视频学习记录

https://www.bilibili.com/video/BV1xG4y1F7nC

  • 组合型的回溯，就是在子集型回溯的基础上增加了一些限制，可以通过剪枝进一步减少搜索范围。

  • 之前的子集可能是找一串字符串的各种子集，组合则是限制了最终的子集长度，内容等。

例题和课后作业代码记录

77. 组合

https://leetcode.cn/problems/combinations/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        path = []
        def dfs(i:int, select_num:int):
            nonlocal ans, path
            # print(ans, path)
            if select_num == k:
                ans.append(path.copy())
                return 

            for num in range(i, k-select_num-1, -1):
                path.append(num)
                dfs(num-1, select_num+1)
                path.pop()
        
        dfs(n, 0)
        return ans

216. 组合总和 III

https://leetcode.cn/problems/combination-sum-iii/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = []
        path = []
        def dfs(index:int, left_n:int):
            nonlocal ans, path 
            left_k = len(path)-k
            if left_k == 0 or left_n <= 0:
                if left_n == 0 and left_k == 0:
                    ans.append(path.copy())
                return 

            for i in range(index, left_k-1, -1): # 这里剪枝了对于数目绝对不够的
                path.append(i)
                dfs(i-1, left_n-i)
                path.pop()
        dfs(9, n)
        return ans

22. 括号生成

https://leetcode.cn/problems/generate-parentheses/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        full_len = 2*n
        
        def dfs(path:str, left:int):
            if len(path) == full_len:
                ans.append(path)
                return 
            
            if left < n:
                dfs(path+"(", left+1)
            
            right = len(path)-left 
            if right < left:
                dfs(path+")", left)


        dfs("", 0)
        return ans

39. 组合总和

https://leetcode.cn/problems/combination-sum/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        ans = []
        path = []

        def dfs(cur_sum:int, start_index:int):
            if cur_sum == target:
                ans.append(path.copy())
                return 
            
            for i, num in enumerate(candidates[start_index:]):
                if cur_sum + num > target:
                    break # candidates排序后，此项开始往后都会超过target
                path.append(num)
                dfs(cur_sum+num, start_index+i)
                path.pop()
        dfs(0, 0)

        return ans