跟随carl代码随想录刷题
语言：python

---

77. 组合

题目：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
👉示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
👉示例 2：
输入：n = 1, k = 1
输出：[[1]]

题目分析——求同一个集合中的组合

• 递归就可以用于解决多层嵌套循环的问题：递归来做层叠嵌套（可以理解是开k层for循环），每一次的递归中嵌套一个for循环。

  • n为100，k为50的情况下，就是递归50层。
  • n相当于树的宽度，k相当于树的深度。

• 图中每次搜索到了叶子节点，我们就找到了一个结果。

• 只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。

参数：

• 定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
• 需要一个参数，为int型变量startIndex，用来记录本层递归中的集合开始遍历位置（集合就是[1,…,n] ）。
  • 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex。

完整代码如下

回溯算法

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        path = []       
        
        def backtracking(n, k, StartIndex):  # 三个参数
            if len(path) == k:  # 终止条件
                res.append(path[:])
                return
            for i in range(StartIndex, n + 1):
                path.append(i)
                backtracking(n, k, i+1)
                path.pop()

        backtracking(n, k, 1)  # StartIndex的初始值为1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

回溯算法——剪枝优化

可以剪枝的地方就在递归中每层for循环所选择的起始位置。如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

• 每次遍历时，StartIndex的终止位置n - (k - len(path)) + 1，而由于range的左闭右开特性，写为n - (k - len(path)) + 2。
  • len(path)为已经选择的元素个数
  • (k - len(path))为还需要原则的元素个数
  • 在该集合中，至多要从n - (k - len(path)) + 1开始遍历。【+1是因为要包含起始位置，做到左闭】
    
    
    path = []
    return res
    

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        path = []       
        
        def backtracking(n, k, StartIndex):  # 三个参数
            if len(path) == k:  # 终止条件
                res.append(path[:])
                return
            for i in range(StartIndex, n-(k-len(path))+2):  # 优化：改一下这个的终止位置
                path.append(i)
                backtracking(n, k, i+1)
                path.pop()

        backtracking(n, k, 1)  # StartIndex的初始值为1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

216. 组合总和 III

题目：找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
👉示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
👉示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
👉示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

题目分析——求同一个集合中的组合

在77题的基础上修改终止条件：
只有满足总和 == n的path才可以放入结果集：

 # 求总和，若`==n`，则计入结果集
sum_ = 0
for i in path:
    sum_ += i
if sum_ == n:
    res.append(path[:])
1
2
3
4
5
6

完整代码如下

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        path = []       
        
        def backtracking(n, k, StartIndex):  # 三个参数
            if len(path) == k:  # 终止条件

                # 求总和，若`==n`，则计入结果集
                sum_ = 0
                for i in path:
                    sum_ += i
                if sum_ == n:
                    res.append(path[:])
                return
                

            for i in range(StartIndex, 9-(k-len(path))+2):  # 优化：改一下这个的终止位置
                path.append(i)
                backtracking(n, k, i+1)
                path.pop()

        backtracking(n, k, 1)  # StartIndex的初始值为1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

17. 电话号码的字母组合

题目：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

👉示例 1：
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
👉示例 2：
输入：digits = “”
输出：[]
👉示例 3：
输入：digits = “2”
输出：[“a”,“b”,“c”]

题目分析——求不同集合之间的组合

• k：

  • 如果是"2, 3"，那就是两层for循环，k=2
  • 如果是"2"，那就是一层for循环，k=1
  • 所以：k = len(digits)

• 全局变量

  • res = [] # 存储结果的结果集
  • path = [] # 叶子节点结果

• 终止条件

  • 如果if index == 输入的数字个数len(digits):
    • 收集结果res.append(path[:])
    • 结束本层递归return

• 单层遍历逻辑

  • 取index指向的数字，
  • 找到对应的字符集
  • 用for循环遍历字符集

• 数字和字母如何映射？

  • 定义一个二维数组

• 输入1、*、#等异常情况

  • 代码中尚未考虑

for循环横向遍历，递归纵向遍历，回溯不断调整结果集。

遍历逻辑：

• 拿到集合一（letter_map[digits[0]]）

• for 元素 in 集合一:

  • 将当前元素存入answer
  • 调用回溯算法，同时拿到集合二（letter_map[digits[1]]）
    • for 元素 in 集合二:
      • 将当前元素存入answer
      • 调用回溯算法——满足终止条件: 将当前answer存入结果集answers
      • 回溯
  • 回溯

• 返回结果集answers

完整代码如下

class Solution:
    def __init__(self):
        self.answers:List[str] = []
        self.answer: str = ''
        self.letter_map = {
            '2':'abc',
            '3':'def',
            '4':'ghi',
            '5':'jkl',
            '6':'mno',
            '7':'pqrs',
            '8':'tuv',
            '9':'wxyz'
        }

    def letterCombinations(self, digits: str) -> List[str]:
        self.answers.clear()
        if not digits:  
            return []
        self.backtracking(digits, 0)
        return self.answers
    
    def backtracking(self, digits:str, index:int) -> None:
        if index == len(digits):  # 当遍历穷尽后的下一层时
            self.answers.append(self.answer)
            return 
        # 单层递归逻辑
        letters:str = self.letter_map[digits[index]]  # 拿到集合
        for letter in letters:  # 拿到集合的元素
            self.answer += letter  # 把当前的集合元素放进结果集
            self.backtracking(digits, index + 1)  # 递归进入另一个集合
            self.answer = self.answer[:-1]  # 回溯

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

39. 组合总和

题目：给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
👉示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
👉示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
👉示例 3：
输入: candidates = [2], target = 1
输出: []

题目分析

本题没有数量要求，可以无限重复，递归没有层数限制。
但总和有限制，相当于间接的个数限制

• startIndex
  • 如果是一个集合来求组合的话，就需要startIndex
  • 如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex
• 数组的长度len(candidate)是for循环的遍历终点
  • for 索引 in (startIndex, len(candidate))
• 因为同一个 数字可以 无限制重复被选取，所以回溯时，StartIndex不用+1，写成本次遍历的i就可以：backtracking(candidates, target, sum_,i)。

完整代码如下

回溯算法

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        path = []       
        
        def backtracking(candidates, target, sum_, StartIndex):  # 三个参数
            
            # 终止条件 
            if sum_ == target:
                res.append(path[:])
                return
            if sum_ > target:
                return
                
            # 单层递归逻辑
            for i in range(StartIndex, len(candidates)):  # 优化：改一下这个的终止位置
                sum_ += candidates[i]  # 求sum_
                path.append(candidates[i])  # 放进单次结果集 

                backtracking(candidates, target, sum_,i)  # 这里不用写i+1了
                
                sum_ -= candidates[i]  # 回溯sum_
                path.pop()  # 回溯单次结果集

        backtracking(candidates, target,0, 0)  # StartIndex的初始值为0
        return res
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

回溯算法——剪枝优化（推荐）

有三个地方更改：

1. 为了剪枝，要提前对数组candidate排序candidate.sort()，否则会报错
2. 在单层递归逻辑判断里面增加一个判断：如果总和sum_＞target: 直接返回return
3. 把终止条件里面的if sum_ > target:语句块删掉

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        path = []       
        
        def backtracking(candidates, target, sum_, StartIndex):  # 三个参数
            
            # 终止条件 
            if sum_ == target:
                res.append(path[:])
                return
            
                
            # 单层递归逻辑
            for i in range(StartIndex, len(candidates)):  # 优化：改一下这个的终止位置
                if sum_ + candidates[i] > target:   # 在单次逻辑里面进行判断，不满足直接返回
                    return
                sum_ += candidates[i]  # 求sum_
                path.append(candidates[i])  # 放进单次结果集 

                backtracking(candidates, target, sum_,i)  # 这里不用写i+1了

                sum_ -= candidates[i]  # 回溯sum_
                path.pop()  # 回溯单次结果集

        candidates.sort()  # 为了剪枝，需要提前排序
        backtracking(candidates, target,0, 0)  # StartIndex的初始值为0
        return res
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

40. 组合总和 II

题目：给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
👉示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
👉示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

题目分析

难点：

1. 每个数字在每个组合中只能使用一次
2. 不能有重复的组合

思路：要在搜索的过程中把重复的组合去掉

• 组合之间需要去重 -> 同一树层上需要去重
• 而同一个组合内部不需要去重 -> 同一条树枝上不需要去重
• 如果candidates[i] == candidates[i - 1] 并且 StartIndex < i（同一树层使用过），就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。此时for循环里就应该做continue的操作。

代码在39题的基础上添加一个去重块（其余代码不变）：

# 对同一树层使用过的元素进行跳过
if candidates[i] == candidates[i-1] and StartIndex < i:
    continue
1
2
3

完整代码如下

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        path = []       
        
        def backtracking(candidates, target, sum_, StartIndex):  # 三个参数
            
            # 终止条件 
            if sum_ == target and path not in res:
                res.append(path[:])
                return
            
                
            # 单层递归逻辑
            for i in range(StartIndex, len(candidates)):  # 优化：改一下这个的终止位置
                if candidates[i] == candidates[i-1] and StartIndex < i:
                    continue
                if sum_ + candidates[i] > target:   # 在单次逻辑里面进行判断，不满足直接返回
                    return
                
                sum_ += candidates[i]  # 求sum_
                path.append(candidates[i])  # 放进单次结果集 

                backtracking(candidates, target, sum_,i+1)  # 这里不用写i+1了

                sum_ -= candidates[i]  # 回溯sum_
                path.pop()  # 回溯单次结果集

        candidates.sort()  # 为了剪枝，需要提前排序
        backtracking(candidates, target,0, 0)  # StartIndex的初始值为0
        return res
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