刷题刷到第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数组去标记每个数字是否被用过。输入样例有两个示例1k3n7输出[[1,2,4]]示例2k3n9输出[[1,2,6], [1,3,5], [2,3,4]]示例2其实是非常典型的递归树展开。第一层选1之后第二层从2开始第一层选2之后第二层从3开始。这种每次只往后看的遍历方式天然就避开了重复组合。动手在纸上把这棵树画一遍比看十遍题解都有用。1.2 必须先想清楚的三个边界第一k不是无限大的。数字只有1到9所以k最大只能等于9。如果k9唯一可能的组合就是[1,2,3,4,5,6,7,8,9]和是45。如果题目给的n比当前k个数的最小和还小或者比最大和还大可以直接返回空列表不需要进入递归。这个预判在性能差的机器上能省下不少时间面试时主动说出来也是加分项。第二结果里的数字必须严格递增吗题目没有明确要求但因为startIndex的存在递归生成的每个组合天然就是递增的。你不需要再额外写排序或去重只要保证递归时从i1开始组合自然有序。第三n可能是很小的数。比如k2n4只有一个组合[1,3][2,2]是非法的因为每个数字最多用一次。k2n3答案是[1,2]。这类边界最好在提交前自己手算一次不要只依赖LeetCode的测试用例毕竟面试时不会有人给你跑测试点。1.3 与组合总和I、II的区别组合总和这个大家族经常被放在一起刷但每题的约束差异其实很大39题candidates是一个给定数组同一个数字可以无限重复使用组合不能重复。40题candidates数组本身可能有重复数组中每个数字在每个组合中只能用一次最终组合不能重复。216题candidates固定为1到9且没有重复每个数字最多用一次k是固定的。我用一个表格把这几个维度的差异列出来复习起来会非常清楚题目候选数字数字能否重复使用结果是否有长度限制去重关键39 组合总和给定数组可以无限次无startIndex传i40 组合总和II给定数组可能含重复每个数字一次无排序used去重77 组合1到n每个数字一次固定kstartIndex传i1216 组合总和III1到9每个数字一次固定kstartIndex传i1从表格能看出216其实就是固定候选范围固定长度的77题再加上一个sum判断。如果你已经把77题拿下了216只是在递归过程中多维护一个求和变量的事。2. 从递归树看回溯的状态设计与终止条件2.1 画一棵选择树k3n7的递归过程我刷回溯题有个雷打不动的习惯代码没写之前先手动画一棵递归树。以k3n7为例整棵树是这样的第一层选1第二层选2第三层选4得到[1,2,4]sum7命中。第三层选5sum8超过7停止。第二层选3第三层选4sum8超过7。第三层选5sum9超过7。第二层选4第三层最小只能选5sum10超过7。第一层选2第二层选3第三层选4sum9超过7。第二层选4第三层选5sum11超过7。第一层选3第二层选4第三层选5sum12超过7。所以唯一的答案就是[1,2,4]。这个例子里绝大多数分支都在第三层因为sum超过7而提前终止只有一条分支真正走到sumn。这个提前终止就是后面要讲的第一处剪枝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之后往下一层递归时可选项只能从i1开始。换句话说startIndex维护了一个只能往后走的约束让每一层决策都建立在前一层选过的数字之后。这其实是一种隐式剪枝搜索空间从排列数P(9,k)降为组合数C(9,k)。别小看这个差别k4的时候P(9,4)3024C(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。这个剪枝之所以成立完全依赖所有数字都是正数这个前提。如果题目某天改成允许负数这个剪枝就不能直接用了。我在本地做过一次简单的调用次数统计。k4n20的时候不做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个数k3说明还需要选2个数。如果i取8后面还可以接着选9能凑成两个数可行如果i取9后面没有第二个数可以选了凑不满。所以上界是9 - 2 1 8。这个地方推导一次就能记住。以后不管候选范围是1到n还是1到9上界都写成n - remaining 1完全通用。我在做77题组合的时候也用了同样写法效果一样。3.3 两处剪枝合并后递归调用次数能少多少把两处剪枝都加上之后我以k3n7为例实际推演过树的分支总数从每个分支都走到第三层缩减到极少几个分支。对于LeetCode给的小规模用例任何写法都能秒过但剪枝的价值不在于这一道题而在于让你养成先缩小搜索空间再动手的思维习惯。后面你会遇到N皇后、解数独这类搜索空间巨大的回溯题剪枝往往是决定算法能不能在超时限制内跑完的关键。在216这种简单题上把剪枝练扎实是性价比很高的一件事。4. 完整实现与提交时需要注意的代码细节4.1 Java版本模板化的写法我用Java写了一个比较规范的版本可以直接贴在LeetCode里跑class Solution { public ListListInteger combinationSum3(int k, int n) { ListListInteger result new ArrayList(); ListInteger path new ArrayList(); backtracking(k, n, 1, 0, path, result); return result; } private void backtracking(int k, int n, int startIndex, int sum, ListInteger path, ListListInteger 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 resultPython版里我把求和等于n换成了剩余值remaining递减到0写起来更直观。判断条件的顺序也可以把remaining 0放在len(path) k之前效果一样只是多走一层。这个版本返回结果时也要用path[:]做拷贝原因和Java完全相同。4.3 提交前的边界自测用例LeetCode的测试用例覆盖比较全但提交前自己把边界用例跑一遍能省下不少罚时。我通常会测这几个k1n9答案是[[9]]。k1n1答案是[[1]]。k3n7答案是[[1,2,4]]。k3n9答案是[[1,2,6],[1,3,5],[2,3,4]]。k9n45唯一组合[1,2,3,4,5,6,7,8,9]。k9n46直接返回[]。k9n44因为k9时唯一可能的组合就是全选和是45所以同样返回[]。这几个用例主要是帮你检查两件事一个是k固定时全集的和是否等于n另一个是sum剪枝在极端值下能不能正确触发。特别是k9的情况如果递归逻辑写得不对很容易在多算几个分支后才返回空结果虽然答案一样但效率会有差别。4.4 时间复杂度和空间复杂度时间复杂度上界是组合数C(9,k)每一层要处理常数时间的操作还要在收集结果时拷贝一个长度为k的列表所以整体是O(C(9,k) * k)。因为候选集只有9个数字这个上界非常小加上剪枝后实际计算量会低于这个值。空间复杂度是O(k)递归栈深度最多为kpath也最多存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上所有基础的回溯题。每次拿到新题先把候选集、可否重复、顺序是否敏感这三个问题想清楚代码框架基本就定下来了。5.3 day156之后的一点刷题心得到第156天还在坚持刷题说实话已经很不容易。这个阶段我最大的体会是不要为了过题而过题。像216这种题AC之后值得再做三件事第一把手画的递归树和代码逐行对应一遍第二把剪枝去掉跑一次对比调用次数第三试着改成39题、40题的变体看看模板哪里需要动。我自己还会在本地给递归函数加一个level参数然后用缩进打印当前path。看到每一层往哪里走了比什么可视化工具都直接。顺便说一句有一些在线的递归可视化工具也能画出类似的效果但自己打印一遍印象更深。我现在做新题仍然会先画树再写码这个习惯帮我避开了大量隐蔽的边界问题。回溯这个专题题目之间的相似度很高但每道题又都会在某个约束上做文章。216是一道很好的标准模板题把它的状态设计、终止条件、剪枝位置吃透后面进入子集、排列、棋盘问题时会顺畅很多。 
长河君 · 2026/9/9 15:44:58 · 阅读 1.2k 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数组去标记每个数字是否被用过。输入样例有两个示例1k3n7输出[[1,2,4]]示例2k3n9输出[[1,2,6], [1,3,5], [2,3,4]]示例2其实是非常典型的递归树展开。第一层选1之后第二层从2开始第一层选2之后第二层从3开始。这种每次只往后看的遍历方式天然就避开了重复组合。动手在纸上把这棵树画一遍比看十遍题解都有用。1.2 必须先想清楚的三个边界第一k不是无限大的。数字只有1到9所以k最大只能等于9。如果k9唯一可能的组合就是[1,2,3,4,5,6,7,8,9]和是45。如果题目给的n比当前k个数的最小和还小或者比最大和还大可以直接返回空列表不需要进入递归。这个预判在性能差的机器上能省下不少时间面试时主动说出来也是加分项。第二结果里的数字必须严格递增吗题目没有明确要求但因为startIndex的存在递归生成的每个组合天然就是递增的。你不需要再额外写排序或去重只要保证递归时从i1开始组合自然有序。第三n可能是很小的数。比如k2n4只有一个组合[1,3][2,2]是非法的因为每个数字最多用一次。k2n3答案是[1,2]。这类边界最好在提交前自己手算一次不要只依赖LeetCode的测试用例毕竟面试时不会有人给你跑测试点。1.3 与组合总和I、II的区别组合总和这个大家族经常被放在一起刷但每题的约束差异其实很大39题candidates是一个给定数组同一个数字可以无限重复使用组合不能重复。40题candidates数组本身可能有重复数组中每个数字在每个组合中只能用一次最终组合不能重复。216题candidates固定为1到9且没有重复每个数字最多用一次k是固定的。我用一个表格把这几个维度的差异列出来复习起来会非常清楚题目候选数字数字能否重复使用结果是否有长度限制去重关键39 组合总和给定数组可以无限次无startIndex传i40 组合总和II给定数组可能含重复每个数字一次无排序used去重77 组合1到n每个数字一次固定kstartIndex传i1216 组合总和III1到9每个数字一次固定kstartIndex传i1从表格能看出216其实就是固定候选范围固定长度的77题再加上一个sum判断。如果你已经把77题拿下了216只是在递归过程中多维护一个求和变量的事。2. 从递归树看回溯的状态设计与终止条件2.1 画一棵选择树k3n7的递归过程我刷回溯题有个雷打不动的习惯代码没写之前先手动画一棵递归树。以k3n7为例整棵树是这样的第一层选1第二层选2第三层选4得到[1,2,4]sum7命中。第三层选5sum8超过7停止。第二层选3第三层选4sum8超过7。第三层选5sum9超过7。第二层选4第三层最小只能选5sum10超过7。第一层选2第二层选3第三层选4sum9超过7。第二层选4第三层选5sum11超过7。第一层选3第二层选4第三层选5sum12超过7。所以唯一的答案就是[1,2,4]。这个例子里绝大多数分支都在第三层因为sum超过7而提前终止只有一条分支真正走到sumn。这个提前终止就是后面要讲的第一处剪枝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之后往下一层递归时可选项只能从i1开始。换句话说startIndex维护了一个只能往后走的约束让每一层决策都建立在前一层选过的数字之后。这其实是一种隐式剪枝搜索空间从排列数P(9,k)降为组合数C(9,k)。别小看这个差别k4的时候P(9,4)3024C(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。这个剪枝之所以成立完全依赖所有数字都是正数这个前提。如果题目某天改成允许负数这个剪枝就不能直接用了。我在本地做过一次简单的调用次数统计。k4n20的时候不做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个数k3说明还需要选2个数。如果i取8后面还可以接着选9能凑成两个数可行如果i取9后面没有第二个数可以选了凑不满。所以上界是9 - 2 1 8。这个地方推导一次就能记住。以后不管候选范围是1到n还是1到9上界都写成n - remaining 1完全通用。我在做77题组合的时候也用了同样写法效果一样。3.3 两处剪枝合并后递归调用次数能少多少把两处剪枝都加上之后我以k3n7为例实际推演过树的分支总数从每个分支都走到第三层缩减到极少几个分支。对于LeetCode给的小规模用例任何写法都能秒过但剪枝的价值不在于这一道题而在于让你养成先缩小搜索空间再动手的思维习惯。后面你会遇到N皇后、解数独这类搜索空间巨大的回溯题剪枝往往是决定算法能不能在超时限制内跑完的关键。在216这种简单题上把剪枝练扎实是性价比很高的一件事。4. 完整实现与提交时需要注意的代码细节4.1 Java版本模板化的写法我用Java写了一个比较规范的版本可以直接贴在LeetCode里跑class Solution { public ListListInteger combinationSum3(int k, int n) { ListListInteger result new ArrayList(); ListInteger path new ArrayList(); backtracking(k, n, 1, 0, path, result); return result; } private void backtracking(int k, int n, int startIndex, int sum, ListInteger path, ListListInteger 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 resultPython版里我把求和等于n换成了剩余值remaining递减到0写起来更直观。判断条件的顺序也可以把remaining 0放在len(path) k之前效果一样只是多走一层。这个版本返回结果时也要用path[:]做拷贝原因和Java完全相同。4.3 提交前的边界自测用例LeetCode的测试用例覆盖比较全但提交前自己把边界用例跑一遍能省下不少罚时。我通常会测这几个k1n9答案是[[9]]。k1n1答案是[[1]]。k3n7答案是[[1,2,4]]。k3n9答案是[[1,2,6],[1,3,5],[2,3,4]]。k9n45唯一组合[1,2,3,4,5,6,7,8,9]。k9n46直接返回[]。k9n44因为k9时唯一可能的组合就是全选和是45所以同样返回[]。这几个用例主要是帮你检查两件事一个是k固定时全集的和是否等于n另一个是sum剪枝在极端值下能不能正确触发。特别是k9的情况如果递归逻辑写得不对很容易在多算几个分支后才返回空结果虽然答案一样但效率会有差别。4.4 时间复杂度和空间复杂度时间复杂度上界是组合数C(9,k)每一层要处理常数时间的操作还要在收集结果时拷贝一个长度为k的列表所以整体是O(C(9,k) * k)。因为候选集只有9个数字这个上界非常小加上剪枝后实际计算量会低于这个值。空间复杂度是O(k)递归栈深度最多为kpath也最多存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上所有基础的回溯题。每次拿到新题先把候选集、可否重复、顺序是否敏感这三个问题想清楚代码框架基本就定下来了。5.3 day156之后的一点刷题心得到第156天还在坚持刷题说实话已经很不容易。这个阶段我最大的体会是不要为了过题而过题。像216这种题AC之后值得再做三件事第一把手画的递归树和代码逐行对应一遍第二把剪枝去掉跑一次对比调用次数第三试着改成39题、40题的变体看看模板哪里需要动。我自己还会在本地给递归函数加一个level参数然后用缩进打印当前path。看到每一层往哪里走了比什么可视化工具都直接。顺便说一句有一些在线的递归可视化工具也能画出类似的效果但自己打印一遍印象更深。我现在做新题仍然会先画树再写码这个习惯帮我避开了大量隐蔽的边界问题。回溯这个专题题目之间的相似度很高但每道题又都会在某个约束上做文章。216是一道很好的标准模板题把它的状态设计、终止条件、剪枝位置吃透后面进入子集、排列、棋盘问题时会顺畅很多。