回溯算法实战：组合与组合总和的递归、剪枝与去重全解析

回溯算法，尤其是组合和组合总和这一组题目，是很多人从“机械地背递归模板”到“真正理解递归在做什么”的分水岭。我刷力扣刷到这里时，第一次意识到回溯不是什么玄学，它本质上是一棵能画在纸上、能一步步跟着走的决策树。这篇就围绕“组合”“组合总和”这两类经典问题，把回溯算法的套路、剪枝技巧、去重原理，以及我实际调试中踩过的坑，一次性讲透。无论你是刚学递归的初学者，还是刷了几十道题但遇到变形就发懵的选手，这篇文章应该都能让你对回溯有更清晰的认识。

1. 回溯算法到底在解决什么问题

1.1 从暴力枚举到智能撤销

回溯算法的本质可以概括成一句话：把问题的解空间看成一颗树，从根节点开始一条路走到黑，如果发现当前路径已经不可能凑出合法答案，就退回上一个岔路口，换个方向再走。

这个“退回再走”的动作，在代码里就叫“撤销选择”。很多同学觉得回溯难，是因为总想给它赋予什么高深的数学含义。实际上它就是穷举法，只不过是一个带“后悔药”的穷举。每走一步都做选择，发现选错了就撤销，再重新选，直到把所有可能的分支都走完。

很多人第一次接触回溯，会觉得“这不就是递归吗”。没错，回溯就是建立在递归之上的暴力搜索。但它和普通递归有一个明显区别：普通递归往往只关心一条路径的结果，回溯关心的是所有满足条件的路径。所以回溯代码里，几乎都会有“记录结果”和“撤销选择”这两步，这是它和普通递归最大的区别。

1.2 组合问题为什么天然适配回溯

组合和排列有一点本质不同：组合不关心顺序。{1, 2}和{2, 1}在组合里是同一个答案。如果题目问的是排列，那这两个都得保留；如果问的是组合，我们就只保留其中一个。

这带来一个很现实的问题：怎么在暴力枚举的过程中自动过滤掉顺序不同的重复答案？

回溯给出的方案是引入一个startIndex参数。它控制着每次递归的循环起点。比如选了数字1之后，下一层递归只能从2开始往后选，永远不能回头选比当前更小的数字。这样一来，{1, 2}会出现，{2, 1}永远不可能出现。

有人可能会问，为什么不直接sort之后再用 set 去重？那样也能做，但效率低不少，而且这属于“先产生垃圾再清理垃圾”的思路。回溯的startIndex是从产生机制上就杜绝了重复，性能要干净得多。

1.3 一套可以套用到所有题目的递归模板

回溯算法之所以好讲，是因为它的代码框架高度统一。不管题目是组合、子集、全排列还是棋盘类，核心骨架都一样：

def backtrack(path, startIndex, ...): if 某个终止条件满足: 记录当前路径 return for 候选 in 可选项: 做选择，把候选加入 path backtrack(path, 新的参数) 撤销选择，把候选从 path 中弹出

这里有两个关键角色：

• path是当前正在探索的路径，它保存的是“已经确定选取的元素”。
• startIndex是下一层递归可选元素的最小下标，它决定了当前这层选择的范围。

很多初学者卡住，就是因为不理解startIndex为什么存在，以及它该传什么值。我的建议是：不要先去抠理论，先拿一道最基础的组合题手写一遍递归树，用笔在纸上把每一层递归里的startIndex标出来，这个参数的含义就一目了然了。

注意：上面模板里的“撤销选择”是千万不能省略的一步。我见过太多人写出了正确的递归逻辑，却因为忘了pop()，导致结果里出现一堆莫名奇妙的超长路径。

2. 组合：先啃下最基础的 LeetCode 77

2.1 题目拆解与为什么 for 循环嵌套派不上用场

LeetCode 77“组合”：给定两个整数n和k，返回范围[1, n]中所有可能的k个数的组合。示例是n = 4, k = 2，输出：

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

很多人第一反应是：这题用几层 for 循环不就行了吗？

问题是k是个变量。k = 2你可以写两层循环，k = 3可以写三层，k = 15呢？总不可能写 15 层循环。for 循环嵌套的层数是固定的，而k一变，嵌套层数就要跟着变——代码是没法动态改变自己的嵌套层数的。

回溯算法在这里做的事情，其实就是在“用递归的深度代替 for 循环的层数”。每一层递归负责决定组合中的某一个位置，递归到第k层就收手记录答案。这样不管k多大，代码结构都不需要变化。

2.2 回溯解法逐行拆解

下面是最经典的写法，我建议初学者把它背下来然后亲手默写几遍：

def combine(n, k): result = [] path = [] def dfs(startIndex): if len(path) == k: result.append(path[:]) return for i in range(startIndex, n + 1): path.append(i) # 做选择 dfs(i + 1) # 递归 path.pop() # 撤销选择 dfs(1) return result

逐行说一些容易被忽略的细节。

第一，为什么终止条件是len(path) == k？因为组合只需要选恰好k个元素。选够了，就不需要继续往下探索了，直接把当前路径保存下来。

第二，为什么递归传入的是i + 1？因为数字不能重复使用。我这一层选了i，下一层只能从i + 1开始选。这正好呼应了前面说的：从机制上杜绝{2, 1}这类重复组合。

第三，为什么记录结果时要用path[:]而不是path？这是新手最容易忽略的地方。path是一个列表对象，后续递归还会继续对它进行append和pop操作。如果直接result.append(path)，你存进去的是同一个对象的引用，等这个对象被改掉，result 里存的所有内容都会跟着变。最后你会发现 result 里全是空列表或同一个奇怪组合。

2.3 剪枝优化：循环上限不是 n

上面的解法已经能 AC（通过所有测试），但还有优化空间。这个优化思路，就是“剪枝”。

先想一想：当前path已经有len(path)个元素，距离k还差k - len(path)个。如果从当前循环起点startIndex到n的剩余元素数量不足k - len(path)个，那么这条分支无论怎么走都凑不出k个数字，根本没意义。

在这种情况下，for 循环其实可以提前终止。循环变量i的最大值不是n，而是：

n - (k - len(path)) + 1

稍微举个例子：n = 4, k = 3，当前path = [2]，还差 2 个元素。i的合理上限是4 - 2 + 1 = 3。也就是说，这一层选i = 3时，后面还有4，凑成[2, 3, 4]，没问题；但如果i = 4，后面只剩0个元素可用，永远凑不满 3 个，这条分支就该被砍掉。

优化后的代码：

def combine(n, k): result = [] path = [] def dfs(startIndex): if len(path) == k: result.append(path[:]) return lastIndex = n - (k - len(path)) + 1 for i in range(startIndex, lastIndex + 1): path.append(i) dfs(i + 1) path.pop() dfs(1) return result

代码只多算了一个lastIndex，但遍历的分支数量肉眼可见地少了一大截。这个思想在后面组合总和里更关键，因为那题的剪枝能帮你省下大量无效递归。

2.4 这个题最容易踩的三个坑

我实际带过不少朋友刷这道题，几乎每个人初版代码都逃不掉下面几个问题。

第一个坑是忘记pop()。这个前面已经强调过。表现是：当len(path) == k时能记录答案，但之后path一直在无限变长，或者输出的组合里混着一堆长度超过k的垃圾路径。解决办法很简单：每次递归返回前，把加进path的那个数字弹出来。

第二个坑是直接result.append(path)。这个也讲过，典型的错误，症状是result里的组合全都一模一样，或者全成了最后一次修改后的样子。把path复制一份再存进去就对了。

第三个坑是边界条件的位数写错。比如循环写成range(startIndex, n)，结果丢掉n本身；或者终止条件写成len(path) == k + 1，导致永远输出不了答案。这种问题我不建议上来就纠结，直接print(path)跟踪一遍就懂了，调试比干想快得多。

3. 组合总和 I：允许重复选取元素后，递归参数发生了什么变化

3.1 题目与核心差异

LeetCode 39“组合总和”：给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。关键约束是：candidates中的数字可以无限制重复被选取。

题目给的示例是candidates = [2, 3, 6, 7]，target = 7。输出是：

[[7], [2, 2, 3]]

注意看，[2, 2, 3]里的2出现了两次。这就是“允许重复选取”的体现。

这一题和基础组合最大的区别就在递归参数的传递上：基础组合里递归传入i + 1，是因为选了当前元素之后，下个位置只能从后面的元素里挑；而这题允许重复使用同一个元素，所以递归传入i，下一层仍然可以从当前元素开始选。

3.2 不加排序的写法与剪枝教训

很多教程直接给你排序后的写法，但我觉得有必要先把“不排序”的版本拿出来，因为这里藏着一个很多教程都没讲清楚的细节。

先看一个不排序、只用 continue 剪枝的版本：

def combinationSum(candidates, target): result = [] path = [] def dfs(startIndex, remain): if remain == 0: result.append(path[:]) return for i in range(startIndex, len(candidates)): if candidates[i] > remain: continue path.append(candidates[i]) dfs(i, remain - candidates[i]) path.pop() dfs(0, target) return result

用if candidates[i] > remain: continue，意味着当前元素比剩余目标还大，选了它之后remain会变成负数，不可能再有合法答案。注意这里必须是continue，不能是break。

为什么不能 break？因为candidates是乱序的。比如candidates = [3, 2, 7]，假设当前remain = 6，candidates[0] = 3不大于6，正常处理；下一个candidates[1] = 2也不大于 6，也正常处理。但如果candidates = [7, 3, 2]且remain = 6，第一个元素7大于remain，此时如果直接break，后面3和2就全被跳过了，会漏掉正确答案。

所以不排序时只能 continue。而排序之后，一旦遇到candidates[i] > remain，后面的元素只会更大，这时才可以用 break 直接跳出循环。这算是这题最容易写错的一个点。

3.3 一个小细节：为什么这里传的是 i 而不是 i + 1

这是我让很多学员“顿悟”的一个点。对比两个代码：

dfs(i + 1, remain - candidates[i]) # 77题，不允许重复 dfs(i, remain - candidates[i]) # 39题，允许重复

看似只差了一个+ 1，但语义完全不同。

传入i + 1，下一层递归只能从当前元素的下一个开始选，于是每个元素至多被选一次。

传入i，下一层递归仍然从当前元素开始选，于是同一个元素可以反复出现。注意这里不是从 0 开始，所以产生的是组合而不是排列。比如[2, 2, 3]会出现，但[2, 3, 2]不会出现，因为第一层选了2之后，第二层起点还是2，虽然能再选2，但选完第二个2之后起点变成了索引 1（值 3），无法回头去选索引 0 的2，所以不可能造出[2, 3, 2]这种顺序交换的重复项。

这一个+ 1的取舍，实际上就是整套回溯算法在“重复与不重复”之间的开关。后面做排列题的时候，你会发现这个开关还会继续变。

4. 组合总和 II：有重复元素时，去重的关键一步

4.1 先排序再去重的逻辑链条

LeetCode 40“组合总和 II”和 39 在题目描述上非常像：给你一组数字和一个目标数，找出所有和为目标的组合。但它有一个关键差异：candidates 里可能有重复元素，且每个数字在每个组合中只能用一次。

题目示例很典型：candidates = [10, 1, 2, 7, 6, 1, 5]，target = 8。注意这里1出现了两次。

如果我们直接用 77 题的思路去解，会得到一堆重复答案，比如[1, 2, 5]和另一个[1, 2, 5]。为什么会有两个？因为两个位置上的1分别被选中了，但它们代表的是同一个组合。

去重的通用原则就一句话：排序是去重的前提。排序之后，相等的数字会相邻排列，我们才能通过“当前元素和上一个元素是否相等”来判断这个值是不是已经在同层被处理过了。

所以这题的第一个动作，一定是candidates.sort()。

4.2 一行 if 搞定树层去重

核心代码精炼到只剩一行判断：

def combinationSum2(candidates, target): candidates.sort() result = [] path = [] def dfs(startIndex, remain): if remain == 0: result.append(path[:]) return for i in range(startIndex, len(candidates)): if i > startIndex and candidates[i] == candidates[i - 1]: continue if candidates[i] > remain: break path.append(candidates[i]) dfs(i + 1, remain - candidates[i]) path.pop() dfs(0, target) return result

需要重点解释的是if i > startIndex and candidates[i] == candidates[i - 1]这行。

这里的逻辑是：在同一层递归的 for 循环里，i == startIndex时，即使在startIndex位置遇到了和前面重复的元素，它也是“必须被尝试”的。因为排序后，重复元素相邻，而当前位置是这一层循环的第一个可选位置，这个分支对应的组合需要保留一次。

但i > startIndex且当前元素和candidates[i - 1]相等时，说明这个值在本层已经被尝试过了，再试一次会产生完全相同的组合。比如排序后candidates = [1, 1, 2, 5, 6, 7, 10]，第一层选择了索引 0 的 1，进入递归后能产生[1, 2, 5]；第一层如果选择索引 1 的 1，后续探索能产生的组合依然是[1, 2, 5]。这两个结果在数值上完全相等，所以索引 1 的这个分支必须被剪掉。

我用一句话记住这个判断：它剪的是“同一层递归里，相同数值的重复分支”。

同时可以看到，因为排序过了，candidates[i] > remain这里可以直接用break而不用continue。这正好呼应上一节说的：排序让剪枝从“不敢断”变成了“放心断”。

4.3 used 数组方案：排列问题的前奏

去重不一定非要i > startIndex这种写法，还有一个常见方案是用布尔数组used标记元素是否被使用过。很多教程在讲排列问题时会用到，其实在组合总和 II 里也能用。

用used数组的写法大致是：

def combinationSum2(candidates, target): candidates.sort() result = [] path = [] used = [False] * len(candidates) def dfs(startIndex, remain): if remain == 0: result.append(path[:]) return for i in range(startIndex, len(candidates)): if i > 0 and candidates[i] == candidates[i - 1] and not used[i - 1]: continue if candidates[i] > remain: break used[i] = True path.append(candidates[i]) dfs(i + 1, remain - candidates[i]) path.pop() used[i] = False dfs(0, target) return result

这里的not used[i - 1]就是“树层去重”的标志：如果上一个相同元素没有在当前这条分支上被用过，说明当前元素这个分支会和上一个元素产生重复组合，剪掉它。

那什么时候用i > startIndex，什么时候用used数组？我的经验是这样的：组合类问题因为有startIndex的存在，用i > startIndex就够了，代码也更短。但一旦做到排列类问题，比如全排列、N 皇后这类需要“从头开始选取元素”的题目，startIndex就不适用了，那时候你只能靠used数组来记录哪些元素已经用过。所以先把used数组的思路理解透，后面刷题的跨度会更平滑。

5. 回溯高频问题排查与调试实录

5.1 症状速查表

我整理了一张表格，基本覆盖了做这三个题时最常见的报错和异常表现。你可以把它当成排查手册用。

5.2 调试技巧：打印 history 与递归层级

很多新手一调试回溯就懵，因为递归一层套一层，print 出来的内容非常乱。我推荐一个很笨但很有效的方法：在path.append和dfs调用前后，打印带缩进的日志。

用一个缩进参数表示当前递归深度，差不多是这样：

def dfs(startIndex, depth): print(" " * depth, "enter startIndex =", startIndex, "path =", path) ... path.append(i) dfs(i + 1, depth + 1) path.pop() print(" " * depth, "back startIndex =", startIndex, "path =", path)

打印出来的结构就是一棵清晰的决策树。你一眼就能看到哪一步忘记撤销了，哪一步的 startIndex 传错了，以及剪枝有没有生效。

这是我在本地 IDE 里最常用的调试手段。不要怕 print 污染代码，调通之后再删掉就行。

5.3 我对三个题目的复杂度实测认知

回溯的复杂度经常被一笔带过，但实际做项目时还是挺重要的。

组合题（77）的答案数量是组合数C(n, k)，每次记录答案要复制长度为k的路径，所以最坏时间复杂度约O(C(n, k) * k)，递归栈深度是O(k)，不算 result 本身的话，空间复杂度是O(k)。

组合总和（39）相对复杂：每个数字可以重复选，递归树的深度理论上能达到target / min(candidates)，每一层有n个可选元素，所以最坏是指数级别。但剪枝带来的实际效果很明显，尤其是排序后遇到candidates[i] > remain就 break，能砍掉大量深分支。

组合总和 II（40）因为加了排序和去重，典型情况下的搜索空间介于 77 和 39 之间，而且由于每个元素只能用一次，树的深度受到数组长度限制，比 39 稳定不少。

我的实测感受是：真正让你超时的通常不是复杂度本身，而是剪枝条件写得太保守。见过很多写法是“结果对了但超时”，只要把剪枝从 continue 改成 break，运行时间能砍掉一大半。

6. 从组合到其他回溯题型的扩展思路

6.1 startIndex 参数传递背后的规律

如果把组合、组合总和 I、组合总和 II 这四道题排在一起看，你会发现一个特别清晰的规律：

这个表是我在刷了十几道回溯题之后慢慢总结出来的。说真的，只要把这四个场景的差异吃透，回溯里 70% 的题目对你来说都只是换了个壳子。

6.2 剪枝的本质：砍掉注定没结果的分支

剪枝这个词听起来很高端，其实干的事情非常朴实：在递归入口处提前判断“这条路走不通”，然后直接返回，不进入循环。

剪枝有两个层次。第一层是在入口处判断，比如组合题里len(path) == k就记录并返回，组合总和里remain == 0就记录并返回，remain < 0就直接放弃。第二层是在 for 循环内部判断，比如组合题算出lastIndex缩小循环范围，组合总和排序后遇到超出的元素就 break。

我建议你写的时候先保证不剪枝也能跑对，再加上剪枝。不然特别容易把剪枝条件写错，反而把正确结果剪没了。我一开始就干过这种事，把candidates[i] > remain写成了>=，结果答案里少了一堆刚好等于剩余目标的情况。

6.3 推荐练习路径与组合数学延伸

如果你跟着这篇文章练，我建议的顺序是：

1. 先手写 77，把回溯模板和撤销选择练熟。
2. 做 39，理解i和i + 1的区别，理解排序对剪枝的影响。
3. 做 40，重点理解同层去重。
4. 最后做全排列 46，感受startIndex失效、used数组上场的场景。

这一套下来，你的回溯手感基本就建立起来了。

另外，如果你对组合本身感兴趣，想更系统地从数学层面理解组合数的增长规律、生成函数这些背景知识，可以翻一翻机械工业出版社引进的《组合数学（原书第5版）》。里面的组合计数、容斥原理这些话题，能帮助你从数学上把握回溯算法到底在搜索多大的解空间，对预估难度和性能瓶颈很有帮助。

我自己刷题那会儿最大的体会是：回溯算法真的不需要死记硬背。你只要保证递归函数里三件事——路径、选择列表、终止条件——一直清晰，然后画一棵小小的递归树，代码往往自己就写出来了。等你把组合、组合总和这一串题目吃透，再遇到子集、分割、棋盘类的题目时，你会有一种“返璞归真”的感觉，因为那些题的本质，仍然是在一棵树上做选择，然后适时回头。