LeetCode 排列，组合，子集问题相关算法题专项整理

78. 子集

回溯法套路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from typing import List


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.res = []

        def backtrack(curRes: List, startIndex: int):
            self.res.append(curRes.copy())
            for i in range(startIndex, len(nums)):
                curRes += [nums[i]]
                backtrack(curRes, i + 1)
                curRes.pop()
        backtrack([], 0)
        return self.res


if __name__ == '__main__':
    solu = Solution()
    print(solu.subsets([1, 2, 3]))

另一种思路是和递归思路比较像，很巧妙。也可以说是动态规划。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from typing import List


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for num in nums:
            res += [item + [num] for item in res]
        return res


if __name__ == '__main__':
    solu = Solution()
    print(solu.subsets([1, 2, 3]))

77. 组合

依然是回溯。只不过，根据条件剪去了一些情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from typing import List


class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.res = []
        self.curRes = []

        def backtrack(start: int, n: int, k: int):
            if (len(self.curRes) == k):
                self.res.append(self.curRes.copy())
                return
            for i in range(start, n + 1):
                self.curRes.append(i)
                backtrack(i + 1, n, k)
                self.curRes.pop()

        backtrack(1, n, k)
        return self.res


if __name__ == '__main__':
    solu = Solution()
    print(solu.combine(4, 2))

46. 全排列

使用回溯，这里使用了备忘录，即 self.used，用来记录是否使用过某一个元素。所以我们在回溯之后要恢复两个东西，一个是备忘录，另一个是 curRes。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from typing import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        self.curRes = []
        self.used = [False] * len(nums)

        def backtrack(nums: List[int]):
            if len(self.curRes) == len(nums):
                self.res.append(self.curRes.copy())
            for i in range(len(nums)):
                if self.used[i]:
                    continue
                self.curRes.append(nums[i])
                self.used[i] = True
                backtrack(nums)
                self.used[i] = False
                self.curRes.pop()

        backtrack(nums)
        return self.res


if __name__ == '__main__':
    s = Solution()
    print(s.permute([1, 2, 3]))

另一种，递归，有一点巧妙：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from typing import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def permutation(nums):
            if len(nums) == 1:
                yield nums[0:1]
            else:
                for perm in permutation(nums[1:]):
                    for i in range(len(perm) + 1):
                        yield perm[:i] + nums[0:1] + perm[i:]
        return list(permutation(nums))


if __name__ == '__main__':
    s = Solution()
    print(s.permute([1, 2, 3]))

90. 子集 II

调试花了一点时间。因为一开始 backtrack(i + 1, nums) 里面的 i 搞成了 start。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from typing import List


class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        self.curRes = []
        nums.sort()

        def backtrack(start: int, nums: List[int]):
            self.res.append(self.curRes.copy())

            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                self.curRes.append(nums[i])
                backtrack(i + 1, nums)
                self.curRes.pop()

        backtrack(0, nums)
        return self.res


if __name__ == "__main__":
    s = Solution()
    print(s.subsetsWithDup([1, 2, 2]))

40. 组合总和 II

使用回溯方法解决：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from typing import List


class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.curRes = []
        self.res = []
        self.trackSum = 0
        candidates.sort()

        def backtrack(start: int, candidates: List[int], target):
            if self.trackSum == target:
                self.res.append(self.curRes.copy())
                return
            if self.trackSum > target:
                return

            for i in range(start, len(candidates)):
                # 除去重复元素的情况
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                self.curRes.append(candidates[i])
                self.trackSum += candidates[i]
                backtrack(i + 1, candidates, target)
                self.trackSum -= candidates[i]
                self.curRes.pop()

        backtrack(0, candidates, target)
        return self.res


if __name__ == "__main__":
    s = Solution()
    print(s.combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))
    # print(s.combinationSum2([2, 5, 2, 1, 2], 5))
    # print(s.combinationSum2([2, 5, 2, 1, 2], 6))

之前使用 dfs 解决，其实也是回溯：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from typing import List


class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(candidates: List[int], target: int, path: List[int], res: List[List[int]]) -> None:
            if target == 0:
                res.append(path)
                return
            for i in range(len(candidates)):
                if target - candidates[i] < 0:
                    break
                if i > 0 and candidates[i] == candidates[i - 1]:
                    continue
                dfs(candidates[i + 1:], target - candidates[i],
                    path + [candidates[i]], res)

        res = []
        candidates.sort()
        dfs(candidates, target, [], res)
        return res


if __name__ == '__main__':
    s = Solution()
    print(s.combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))
    print(s.combinationSum2([2, 5, 2, 1, 2], 5))
    print(s.combinationSum2([2, 5, 2, 1, 2], 6))

47. 全排列 II

回溯加上剪枝。这里的剪枝有一定的技巧性。

对于剪枝的判断：重复元素，前面的元素一定要在当前元素之前使用。

还有，一定要先给数组排序！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from typing import List


class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.curRes = []
        self.res = []
        self.used = [False] * len(nums)
        nums.sort()

        def backtrack(nums: List[int]):
            if len(self.curRes) == len(nums):
                self.res.append(self.curRes.copy())

            for i in range(len(nums)):
                if self.used[i]:
                    continue
                if i > 0 and nums[i] == nums[i - 1] and not self.used[i - 1]:
                    continue
                self.curRes.append(nums[i])
                self.used[i] = True
                backtrack(nums)
                self.used[i] = False
                self.curRes.pop()

        backtrack(nums)
        return self.res


if __name__ == "__main__":
    s = Solution()
    # print(s.permuteUnique([1, 1, 2]))
    print(s.permuteUnique([3, 3, 0, 3]))

39. 组合总和

回溯的时候，start 变了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from typing import List


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.curRes = []
        self.res = []
        self.trackSum = 0
        candidates.sort()

        def backtrack(start: int, nums: List[int], target: int):
            if self.trackSum == target:
                self.res.append(self.curRes.copy())
            if self.trackSum > target:
                return

            for i in range(start, len(nums)):
                self.curRes.append(nums[i])
                self.trackSum += nums[i]
                backtrack(i, nums, target)
                self.trackSum -= nums[i]
                self.curRes.pop()

        backtrack(0, candidates, target)
        return self.res


if __name__ == '__main__':
    s = Solution()
    print(s.combinationSum([2, 7, 6, 3, 5, 1], 9))

之前的做法，类似：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from typing import List


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(candidates: List[int], target: int, path: List[int], res: List[List[int]]) -> None:
            if target == 0:
                res.append(path)
                return
            for i in range(len(candidates)):
                if target - candidates[i] < 0:
                    break
                dfs(candidates[i:], target - candidates[i],
                    path + [candidates[i]], res)

        res = []
        candidates.sort()
        dfs(candidates, target, [], res)
        return res


if __name__ == '__main__':
    s = Solution()
    print(s.combinationSum([2, 7, 6, 3, 5, 1], 9))

216. 组合总和 III

依然是回溯加上简单的剪枝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from typing import List


class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.curRes = []
        self.res = []
        self.trackSum = 0
        self.trackCount = 0

        def backtrack(start: int, k: int, n: int):
            if self.trackSum == n and self.trackCount == k:
                self.res.append(self.curRes.copy())

            if self.trackSum > n or self.trackCount > k:
                return

            for i in range(start, 10):
                self.curRes.append(i)
                self.trackSum += i
                self.trackCount += 1
                backtrack(i + 1, k, n)
                self.trackCount -= 1
                self.trackSum -= i
                self.curRes.pop()

        backtrack(1, k, n)
        return self.res


if __name__ == "__main__":
    solu = Solution()
    print(solu.combinationSum3(3, 7))
    print(solu.combinationSum3(3, 9))