LeetCode 216组合总和III：回溯算法剪枝与去重详解-平芜编程栈

刷题刷到第156天，题目编号是216。今天这题是回溯专题里的组合总和III，问题描述短得像散文：从数字1到9里选k个数，每个数字最多用一次，让这些数的和等于n，返回所有可能的组合。我一开始以为这就是组合总和的换皮题，真正上手才发现，这题把回溯算法里最容易出错的三个点——层数控制、组合去重、剪枝边界——全部揉在了一起。这篇文章就把我完整的思考过程、代码实现和两处剪枝的推导写清楚，给正在刷回溯专题的朋友一个可以直接参考的样例。

先说这题适合谁看：如果你已经刷过77题组合或者39题组合总和，想进一步搞懂"什么时候用startIndex、什么时候用used数组、什么时候剪枝"，那216是一个很好的承上启下题目；如果你刚开始接触回溯，也不用怕，这题的状态变量非常少，非常适合用来理解递归树是怎么长出来的。下面我按自己实际做题的顺序来写，先拆题，再画树，再剪枝，最后给代码。

1. 题意拆解：这题到底在求什么，坑在哪里

1.1 题目描述与输出要求

LeetCode-216的完整表述是：找出所有相加之和为 n 的 k 个数的组合，且满足：只使用数字1到9；每个数字最多使用一次。返回所有可能的有效组合的列表，组合中的数字可以按任意顺序排列。

注意"组合"两个字很关键。[1,2,4]和[2,1,4]在数学意义上属于同一个组合，题目既然叫组合而不是排列，结果里就不能同时出现这两个。这一点决定了整个算法的走向：必须用startIndex来保持选择顺序，而不是像全排列那样用一个used数组去标记每个数字是否被用过。

输入样例有两个：

示例1：k=3，n=7，输出[[1,2,4]]
示例2：k=3，n=9，输出[[1,2,6], [1,3,5], [2,3,4]]

示例2其实是非常典型的递归树展开。第一层选1之后，第二层从2开始；第一层选2之后，第二层从3开始。这种"每次只往后看"的遍历方式，天然就避开了重复组合。动手在纸上把这棵树画一遍，比看十遍题解都有用。

1.2 必须先想清楚的三个边界

第一，k不是无限大的。数字只有1到9，所以k最大只能等于9。如果k=9，唯一可能的组合就是[1,2,3,4,5,6,7,8,9]，和是45。如果题目给的n比当前k个数的最小和还小，或者比最大和还大，可以直接返回空列表，不需要进入递归。这个预判在性能差的机器上能省下不少时间，面试时主动说出来也是加分项。

第二，结果里的数字必须严格递增吗？题目没有明确要求，但因为startIndex的存在，递归生成的每个组合天然就是递增的。你不需要再额外写排序或去重，只要保证递归时从i+1开始，组合自然有序。

第三，n可能是很小的数。比如k=2，n=4，只有一个组合[1,3]；[2,2]是非法的，因为每个数字最多用一次。k=2，n=3，答案是[1,2]。这类边界最好在提交前自己手算一次，不要只依赖LeetCode的测试用例，毕竟面试时不会有人给你跑测试点。

1.3 与组合总和I、II的区别

组合总和这个大家族经常被放在一起刷，但每题的约束差异其实很大：

39题：candidates是一个给定数组，同一个数字可以无限重复使用，组合不能重复。
40题：candidates数组本身可能有重复，数组中每个数字在每个组合中只能用一次，最终组合不能重复。
216题：candidates固定为1到9，且没有重复，每个数字最多用一次，k是固定的。

我用一个表格把这几个维度的差异列出来，复习起来会非常清楚：

题目	候选数字	数字能否重复使用	结果是否有长度限制	去重关键
39 组合总和	给定数组	可以无限次	无	startIndex传i
40 组合总和II	给定数组（可能含重复）	每个数字一次	无	排序+used去重
77 组合	1到n	每个数字一次	固定k	startIndex传i+1
216 组合总和III	1到9	每个数字一次	固定k	startIndex传i+1

从表格能看出，216其实就是"固定候选范围+固定长度"的77题，再加上一个sum判断。如果你已经把77题拿下了，216只是在递归过程中多维护一个求和变量的事。

2. 从递归树看回溯的状态设计与终止条件

2.1 画一棵选择树：k=3，n=7的递归过程

我刷回溯题有个雷打不动的习惯：代码没写之前，先手动画一棵递归树。以k=3，n=7为例，整棵树是这样的：

第一层选1
- 第二层选2
  - 第三层选4，得到[1,2,4]，sum=7，命中。
  - 第三层选5，sum=8，超过7，停止。
- 第二层选3
  - 第三层选4，sum=8，超过7。
  - 第三层选5，sum=9，超过7。
- 第二层选4
  - 第三层最小只能选5，sum=10，超过7。
第一层选2
- 第二层选3
  - 第三层选4，sum=9，超过7。
- 第二层选4
  - 第三层选5，sum=11，超过7。
第一层选3
- 第二层选4
  - 第三层选5，sum=12，超过7。

所以唯一的答案就是[1,2,4]。这个例子里，绝大多数分支都在第三层因为sum超过7而提前终止，只有一条分支真正走到sum==n。这个"提前终止"就是后面要讲的第一处剪枝：if (sum > n) return。

手动展开这棵树最大的价值在于，你会意识到：不需要等到path.size() == k才检查sum，因为一旦sum已经超过目标值，即使还没凑满k个数，后面的数只会更大（1到9是递增的），永远不可能回到目标值。所以sum超标时可以直接返回。

2.2 为什么startIndex是组合去重的关键

组合问题最怕的就是重复。如果没有startIndex，从[1,2,4]出发，回溯后第一层选2时，第二层可能还会再选1，生成[2,1,4]，而这个组合和[1,2,4]本质相同。startIndex的作用就是：当你在某一层已经选到数字i之后，往下一层递归时，可选项只能从i+1开始。

换句话说，startIndex维护了一个"只能往后走"的约束，让每一层决策都建立在前一层选过的数字之后。这其实是一种隐式剪枝：搜索空间从排列数P(9,k)降为组合数C(9,k)。别小看这个差别，k=4的时候，P(9,4)=3024，C(9,4)=126，差了二十多倍。

这个道理说起来简单，真写代码时很容易错写成backtracking(k, n, i, sum, path)而不是backtracking(k, n, i + 1, sum, path)。一旦写成i，同一个数字会被重复选，题目里"每个数字最多使用一次"的约束就被破坏了。

2.3 终止条件怎么设置更合理

关于终止条件，网上有两种主流写法：

第一种：递归入口先判断if (path.size() == k && sum == n)再收集结果。这是最直白的写法，但等于把所有分支都走到底再判断，效率偏低。

第二种：把终止条件拆成两件事。先看sum > n就返回；再看path.size() == k时是否sum == n。这种写法可以在递归早期就把超和分支砍掉，实际运行时会少很多无效调用。

我推荐第二种。因为数字范围限定在1到9，每一层可选择的数量本来就不多，如果不在sum超过n时及时回头，很多分支到了最后一层才发现超了，白白浪费递归调用。

关于sum的传递方式，我习惯把它作为递归参数传下去，而不是定义成一个全局成员变量。这样每个递归分支都拥有自己独立的sum副本，不需要在回溯时手动减回去，代码出错的概率更低。如果你更习惯维护全局sum，记得在递归返回后执行sum -= i，这一步漏掉的话，bug会非常隐蔽而且很难排查。

3. 剪枝的两种姿势，一个都不能少

3.1 第一刀：sum超过目标值直接退出

第一处剪枝就是递归函数一进来的if (sum > n) return。放在所有逻辑的最前面，不区分当前层数。为什么放在入口而不是循环里判断？因为无论是进入更深层递归之前，还是从更深层返回之后，只要sum超标，当前这一段路径已经不可能产生有效答案，继续下去没有任何意义。

这里有一个容易忽略的细节：数字1到9都是正整数，并且随着startIndex增加，后续选到的数字只会越来越大。所以一旦sum超过了n，无论后面怎么加，sum都只会继续变大，不可能变回n。这个剪枝之所以成立，完全依赖"所有数字都是正数"这个前提。如果题目某天改成允许负数，这个剪枝就不能直接用了。

我在本地做过一次简单的调用次数统计。k=4，n=20的时候，不做sum剪枝，递归树会遍历几乎所有组合；加上sum剪枝后，很多第三层、第四层的分支在进入更深处之前就被拦截了。肉眼观察就是提交耗时从两三毫秒降到接近零毫秒。LeetCode的用例规模很小，这个差异不一定能明显体现在运行时间上，但面试时能主动说出"这里还能剪枝"，和只会套模板的候选人差距一下就拉开了。

3.2 第二刀：for循环上界的精确收缩

第二处剪枝很多人会忽略。很多模板题解里for循环都写成for (int i = startIndex; i <= 9; i++)，这在k比较小的时候没问题，但k接近9时，会有大量无意义的for循环迭代。

正确的做法是计算当前还需要选多少个数：remaining = k - path.size()。假设可选范围是1到9，如果从某个i开始，剩余可选的数字个数已经少于还需要选的个数，那么这个i以及之后的i都不可能凑满k个数，直接不进循环。

因此，for循环上界应该是9 - (k - path.size()) + 1。换个说法：i最大只能到9 - remaining + 1。举个例子：当前path已经有1个数，k=3，说明还需要选2个数。如果i取8，后面还可以接着选9，能凑成两个数，可行；如果i取9，后面没有第二个数可以选了，凑不满。所以上界是9 - 2 + 1 = 8。

这个地方推导一次就能记住。以后不管候选范围是1到n还是1到9，上界都写成n - remaining + 1，完全通用。我在做77题组合的时候也用了同样写法，效果一样。

3.3 两处剪枝合并后，递归调用次数能少多少

把两处剪枝都加上之后，我以k=3，n=7为例实际推演过，树的分支总数从"每个分支都走到第三层"缩减到极少几个分支。对于LeetCode给的小规模用例，任何写法都能秒过，但剪枝的价值不在于这一道题，而在于让你养成"先缩小搜索空间再动手"的思维习惯。

后面你会遇到N皇后、解数独这类搜索空间巨大的回溯题，剪枝往往是决定算法能不能在超时限制内跑完的关键。在216这种简单题上把剪枝练扎实，是性价比很高的一件事。

4. 完整实现与提交时需要注意的代码细节

4.1 Java版本：模板化的写法

我用Java写了一个比较规范的版本，可以直接贴在LeetCode里跑：

class Solution { public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> result = new ArrayList<>(); List<Integer> path = new ArrayList<>(); backtracking(k, n, 1, 0, path, result); return result; } private void backtracking(int k, int n, int startIndex, int sum, List<Integer> path, List<List<Integer>> result) { // 第一处剪枝：和已经超过目标值，后续只会更大 if (sum > n) { return; } // 个数凑满 k 个，判断是否命中 if (path.size() == k) { if (sum == n) { result.add(new ArrayList<>(path)); } return; } // 第二处剪枝：for 循环上界随剩余个数收缩 for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { path.add(i); sum += i; backtracking(k, n, i + 1, sum, path, result); sum -= i; path.remove(path.size() - 1); } } }

几个值得注意的位置：

result.add(new ArrayList<>(path))这里一定要拷贝一份path。因为后续递归会对path做回溯修改，如果直接add(path)，最终result里存的是同一个对象的引用，回溯结束后这个对象会被清空，result会变成一堆空列表。这是回溯新人最容易踩的坑，没有之一。
上面代码里sum是作为参数传进递归的，每一层递归都持有自己的sum副本，所以递归返回后不需要也不能靠sum字段做恢复。但如果你已经把sum处理成全局变量，记得要在回溯时sum -= i。
循环里的上界用了剪枝后的写法9 - (k - path.size()) + 1。里面的k和path.size()都是可变值，每次循环前都要重新计算，所以直接写在循环条件里最安全，不要提前缓存成局部变量，否则path变化后上界不会跟着更新。

4.2 Python版本：一种更简洁的等价写法

如果你用Python刷题，可以写成下面这样。它的核心逻辑和Java完全一致，只是列表的切片让回溯更顺手：

class Solution: def combinationSum3(self, k: int, n: int) -> List[List[int]]: result = [] path = [] def backtrack(start: int, remaining: int) -> None: if len(path) == k: if remaining == 0: result.append(path[:]) return if remaining < 0: return for i in range(start, 10 - (k - len(path)) + 1): path.append(i) backtrack(i + 1, remaining - i) path.pop() backtrack(1, n) return result

Python版里我把"求和等于n"换成了"剩余值remaining递减到0"，写起来更直观。判断条件的顺序也可以把remaining < 0放在len(path) == k之前，效果一样，只是多走一层。这个版本返回结果时也要用path[:]做拷贝，原因和Java完全相同。

4.3 提交前的边界自测用例

LeetCode的测试用例覆盖比较全，但提交前自己把边界用例跑一遍，能省下不少罚时。我通常会测这几个：

k=1，n=9：答案是[[9]]。
k=1，n=1：答案是[[1]]。
k=3，n=7：答案是[[1,2,4]]。
k=3，n=9：答案是[[1,2,6],[1,3,5],[2,3,4]]。
k=9，n=45：唯一组合[1,2,3,4,5,6,7,8,9]。
k=9，n=46：直接返回[]。
k=9，n=44：因为k=9时唯一可能的组合就是全选，和是45，所以同样返回[]。

这几个用例主要是帮你检查两件事：一个是k固定时全集的和是否等于n，另一个是sum剪枝在极端值下能不能正确触发。特别是k=9的情况，如果递归逻辑写得不对，很容易在多算几个分支后才返回空结果，虽然答案一样，但效率会有差别。

4.4 时间复杂度和空间复杂度

时间复杂度上界是组合数C(9,k)，每一层要处理常数时间的操作，还要在收集结果时拷贝一个长度为k的列表，所以整体是O(C(9,k) * k)。因为候选集只有9个数字，这个上界非常小，加上剪枝后实际计算量会低于这个值。

空间复杂度是O(k)，递归栈深度最多为k，path也最多存k个数。result占用的空间一般不计入算法本身的空间复杂度，但如果面试官专门问到输出空间，可以补充说明输出结果本身可能占O(C(9,k) * k)。

5. 跳出216：回溯家族题型对比与通用解题框架

5.1 我把回溯题归成的四类

刷了这么多回溯题之后，我习惯把回溯家族分成四类：组合、排列、子集、棋盘/分割类。它们共享同一个模板，区别只在于三件事：选择列表是什么、下一层递归从哪个位置开始、终止条件是什么。

组合类：需要startIndex，元素顺序无关，去重靠"只往后选"。
排列类：需要used数组或每次从头扫描，元素顺序有关。
子集类：需要startIndex，但没有长度限制，每个节点都可以收集答案。
棋盘/分割类：典型如N皇后、分割回文串，状态转移更复杂，但本质也是DFS加状态撤销。

216属于组合类的典型代表。如果你能独立写出216，下一个更值得做的是40题组合总和II，它引入了"candidates本身有重复"这个新问题，需要在排序后用used数组做同层去重。再往下可以挑战47题全排列II，去重逻辑会更绕，但理解了"树层去重"和"树枝去重"的区别后，基本就不会再错。

5.2 从216迁移到其他题的三个操作

这块是我自己总结的，遇到变体题时直接套用：

第一，如果题目允许同一个数字无限重复使用，比如39题，只要把递归参数从i + 1改成i即可。因为允许重复，当前数字选完之后，下一层依然可以从i开始选。

第二，如果候选数组本身有重复数字，比如40题，就必须先对candidates排序，然后在for循环里判断if (i > startIndex && candidates[i] == candidates[i - 1]) continue，跳过同一层的重复分支。这个判断解决的是"同一层去重"，而不是"同一路径去重"，两者的区别是回溯里最容易绕晕的地方。

第三，如果题目不问组合而问排列，比如46题全排列，就不能用startIndex了，因为排列里每个位置都可以放任何一个未使用过的数字。此时需要used数组来标记某个下标的数字是否已经在当前排列中出现过，递归参数里就没有startIndex。

这三个操作几乎能解决LeetCode上所有基础的回溯题。每次拿到新题，先把候选集、可否重复、顺序是否敏感这三个问题想清楚，代码框架基本就定下来了。