wbfwonderful's Blog
【代码随想录】回溯1-组合问题
wbfwonderful Lv4
  2025-07-10 14:17:44   2025-07-10 22:41:17    2.6k 字  10 分钟  

回溯法

回溯是递归的副产品，只要有递归就会有回溯。回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。通常可以解决以下问题：

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N皇后，解数独等等

回溯法解决的问题都可以抽象为树形结构。因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

回溯法模板

  • 回溯函数返回值和参数
    • 回溯算法需要的参数不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
  • 回溯函数终止条件
    • ？
  • 回溯搜索的遍历过程
    • 回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

image

1
2
3
4
5
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
}

总结起来模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

77. 组合

link

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

思路

直接的思路为 k 重循环。但是 k 很大时就写不出来了。

要解决 n 为 100，k 为 50 的情况，暴力写法需要嵌套 50 层 for 循环，那么回溯法就用递归来解决嵌套层数的问题。

组合问题可以抽象为：

image

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。图中可以发现 n 相当于树的宽度，k 相当于树的深度。那么如何在这个树上遍历，然后收集到我们要的结果集呢？图中每次搜索到了叶子节点，我们就找到了一个结果。

  • 递归函数的返回值和参数：n 和 k，以及一个起始索引 start，用于指定从哪个位置开始取数。此外，还需要两个全局变量，一个用于存放所有的结果 res，另一个用于存放当前路径下的结果 cur。
  • 递归函数的终止条件：当前路径下的结果长度等于 k，即 len(cur) == k，就说明到了叶子节点。
  • 单层搜索的过程：回溯法的搜索过程就是一个树型结构的遍历过程，for 循环用来横向遍历（当层），递归的过程是纵向遍历。所以 for 循环从 start 开始遍历，然后递归下一层。

代码如下，注意两个点：

  • 把当前结果 cur 加入最终结果 res 时，不能直接 res.append(cur)，因为 list 是可变对象，这样写是深拷贝，加入 res 的是引用。需要写成 res.append(cur[:]) 或 res.append(list(cur))。
  • 第一次调用回溯函数时，start 应该是 1，不是 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        cur = []
        def backtrack(n, k, start):
            if len(cur) == k:
                res.append(cur[:])
                return
            
            for i in range(start, n+1):
                # 把当前节点加入到结果中
                cur.append(i)
                # 处理下一层
                backtrack(n, k, i + 1)
                # 将当前元素移除，然后处理下一个元素
                cur.pop()

        backtrack(n, k, 1)

        return res

减枝优化

例如 n = 4，k = 4 的话，那么第一层 for 循环的时候，从元素 2 开始的遍历都没有意义了。 在第二层 for 循环，从元素 3 开始的遍历都没有意义了。

image

所以，可以剪枝的地方就在递归中每一层的 for 循环所选择的结束位置。优化过程为：

  • 已经有的元素个数 len(cur)
  • 还需要的个数 k - len(cur)
  • 当前集合最多允许的结束位置 n - (k - len(cur)) + 1。
    • 后面剩下的要留给后续层来遍历，即后面还需要剩下 k - len(cur) 个元素
    • 注意这个 +1，例如在第二层，len(cur) == 1，还需要 3，从后往前数 3 个，只能到 2（是在 [1, 2, 3, 4] 里面），n - (k - len(cur)) == 1，所以这里有一个 +1。注意这里不是索引，而是要选的数字。
    • 此外，由于 range 是左闭右开，所以代码中是 +2。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        cur = []
        def backtrack(n, k, start):
            if len(cur) == k:
                res.append(cur[:])
                return
            # 减枝，注意这个 +2
            for i in range(start, n - (k - len(cur)) + 2):
                # 把当前节点加入到结果中
                cur.append(i)
                # 处理下一层
                backtrack(n, k, i + 1)
                # 将当前元素移除，然后处理下一个元素
                cur.pop()

        backtrack(n, k, 1)

        return res

17.电话号码和字母的组合

link

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

image

思路

类似于 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
26
27
28
29
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        m = {
            2: "abc",
            3: "def",
            4: "ghi",
            5: "jkl",
            6: "mno",
            7: "pqrs",
            8: "tuv",
            9: "wxyz"
        }
        res = []
        cur = []

        def backtract(digits, index):
            if len(digits) == 0:
                return
            if len(cur) == len(digits):
                res.append("".join(cur))
                return
            cur_str = m[int(digits[index])]
            for i in cur_str:
                cur.append(i)
                backtract(digits, index+1)
                cur.pop()
        
        backtract(digits, 0)
        return res

216.组合总和III

link

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字 1 到 9，每个数字 最多使用一次。返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

输入: 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

思路

同样类似于 77.组合，递归三部曲：

  • 参数和返回值：参数为当前层的起始值 start（应该从哪个数开始选）和当前的综合 total（避免多次调用 sum 函数）
  • 递归终止条件：当前结果 cur 长度为 k，并且和为 n，则将当前结果加入到 res；如果和大于 n 或者长度大于 k，则直接返回（剪枝操作）
  • 递归核心逻辑：和 77.组合 类似。
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]]:
        res = []
        cur = []

        def backtrack(start, total):
            if len(cur) > k or total > n:
                return
            if len(cur) == k and total == n:
                res.append(cur[:])
                return

            for i in range(start, 10):
                cur.append(i)
                backtrack(i + 1, total + i)
                cur.pop()

        backtrack(1, 0)
        return res

39.组合总和

link
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

思路

类似于上一题，只不过递归的主逻辑中，再次递归时，数组访问的起点可以和当前相同（因为可以重复选某些数字）

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

        def backtrack(start, total):
            if total == target:
                res.append(cur[:])
                return
            elif total > target:
                return 

            for i in range(start, len(candidates)):
                cur.append(candidates[i])
                backtrack(i, total+candidates[i])
                cur.pop()
            
        backtrack(0, 0)
        return res

40.组合总和II

link

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次 。注意：解集不能包含重复的组合。candidates 中可能有重复的元素。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

思路

和上一题一样，只不过添加了不能选取重复数字的限制。只需要在递归的逻辑中更改即可。但是注意，candidates 中可能有重复元素，例如 candidates = [1,1,2]，target = 3，两个 1 都会被选，所以结果为 [[1,2],[1,2]]。

所以首先将 candidates 排序，然后判断当前数字是否和上一个相同，如果相同就跳过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        cur = []
        candidates.sort()
        def backtrack(start, total):
            if total == target:
                res.append(cur[:])
                return
            elif total > target:
                return 

            for i in range(start, len(candidates)):
                # 判断当前数字是否和上一个相同，如果相同就跳过
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                cur.append(candidates[i])
                backtrack(i+1, total+candidates[i])
                cur.pop()
            
        backtrack(0, 0)
        return res
【代码随想录】回溯1-组合问题
Leetcode/backtrack1/
作者
wbfwonderful
发布于
2025-07-10 14:17
许可
  1. 1. 回溯法
    1. 1.1. 回溯法模板
  2. 2. 77. 组合
    1. 2.1. 思路
    2. 2.2. 减枝优化
  3. 3. 17.电话号码和字母的组合
    1. 3.1. 思路
  4. 4. 216.组合总和III
    1. 4.1. 思路
  5. 5. 39.组合总和
    1. 5.1. 思路
  6. 6. 40.组合总和II
    1. 6.1. 思路
  1. 1. 回溯法
    1. 1.1. 回溯法模板
  2. 2. 77. 组合
    1. 2.1. 思路
    2. 2.2. 减枝优化
  3. 3. 17.电话号码和字母的组合
    1. 3.1. 思路
  4. 4. 216.组合总和III
    1. 4.1. 思路
  5. 5. 39.组合总和
    1. 5.1. 思路
  6. 6. 40.组合总和II
    1. 6.1. 思路