回溯算法这个词只要刷过LeetCode基本都绕不开而“组合”和“组合总和”这两类题几乎被公认为回溯入门的必修课。我自己带过不少学弟学妹也帮人改过很多次代码最大的感触是模板大家都会背真到自己上手写的时候却在“什么时候撤销选择”“为什么这里传 i 而不是 start”“排序到底剪了什么”这几个地方反复卡壳。这篇内容我会用 77. 组合、39. 组合总和、40. 组合总和Ⅱ 这三道题作为线索把回溯的底层逻辑掰开揉碎讲清楚。它适合两类人看一是刚接触回溯、对这些题似懂非懂的初学者二是背过模板但做题时总出边界问题的进阶者。看完之后希望你不仅能写出这三道题还能真正理解为什么代码要长成这个样子遇到变种题知道从哪里下手。1. 回溯框架的本质选择、递归、撤销的三步循环1.1 回溯就是带“后悔药”的深度优先搜索回溯算法的本质其实是一棵隐式的递归树上的深度优先遍历。我们说“隐式”是因为这棵树并不存在内存里而是通过递归调用栈一层层展开的。每一层递归代表一次“决策”每一条从根到叶子的路径就是一个完整的候选答案。之所以叫“回溯”核心就在“回”这个字上当一条路径走到底发现不满足条件或者已经收集到一个答案时你要退回到上一个岔路口换一个分支继续尝试。这个退回动作的实现方式就是在递归返回后把之前做的选择撤销掉。所有回溯题都遵循一个固定的三步循环做选择把当前可选元素加入路径path递归带着这个选择继续向下一层探索撤销选择把刚才加入的元素弹出恢复到选择前的状态为尝试下一个分支做准备。这个套路听起来简单但真正让它成立的是第 1 步和第 3 步的严格对称。你加进去了什么就必须在递归返回后原样弹出来。如果只加不弹路径就会被污染后面的分支会带着上一个分支的残留数据结果自然全错。1.2 为什么组合问题是理解回溯的最佳载体回溯能解的题很多排列、子集、分割回文串、N皇后、数独……但组合问题绝对是最适合入门的那一个。为什么因为它的递归树结构最简单——每一层只负责“选一个数”没有复杂的棋盘约束没有重复状态的推导你只需要盯住“起点”和“路径”两件事。拿 77. 组合来说题目是给定 1 到 n 这 n 个数字返回所有长度为 k 的组合。n 4, k 2 时答案就是[1,2] [1,3] [1,4] [2,3] [2,4] [3,4]注意这里 [1,2] 和 [2,1] 算同一个组合所以我们在选第二个数时绝对不能回到 1 之前的位置否则就会出现重复。这就是组合和排列最本质的区别也是整篇文章反复要强调的“起点控制”问题。2. 组合LeetCode 77从递归树看起点控制2.1 画一棵递归树一切都清楚了对于 n 4, k 2我们第一层可以在 1、2、3、4 中选一个第二层必须从“当前选的数字之后”再选一个。递归树长这样[] 1 2 3 4 / | \ / | | 2 3 4 3 4 4第一层选了 1第二层只能从 2、3、4 中选第一层选了 2第二层只能从 3、4 中选。每一条从根到叶子的路径就是一个组合。这里有一个非常关键的细节第二层的起点是动态的它永远等于“上一层选的那个数字 1”。这就是为什么递归函数需要一个 start 参数而它的作用就是告诉当前层“你可以从哪个位置开始选不能再往左回头了。”2.2 标准写法与剪枝优化基础的 Python 写法如下class Solution: def combine(self, n: int, k: int) - List[List[int]]: res [] path [] def backtrack(start: int) - None: # 路径中已经有 k 个数收集答案 if len(path) k: res.append(path[:]) return # 从 start 开始枚举本轮可选的数字 for i in range(start, n 1): path.append(i) # 做选择 backtrack(i 1) # 递归下一层起点是 i1 path.pop() # 撤销选择 backtrack(1) return res这个写法是最朴素的回溯不包含任何剪枝。它的效率其实一般因为很多递归分支根本走不到叶子节点就会被白跑一遍。举个最简单的例子n 4, k 4第一层选了 4 之后剩下已经没有足够的数字凑满 4 个了但递归还是会继续往下走。剪枝的思路很简单当前路径已经有 len(path) 个数还差 k - len(path) 个。这剩下的几个数至少得有地方放所以本轮 i 的最大值不能超过 n - (k - len(path)) 1。class Solution: def combine(self, n: int, k: int) - List[List[int]]: res [] path [] def backtrack(start: int) - None: if len(path) k: res.append(path[:]) return # 剪枝i 最多只能到 n - (k - len(path)) 1 for i in range(start, n - (k - len(path)) 2): path.append(i) backtrack(i 1) path.pop() backtrack(1) return res我见过很多初学者对这段剪枝范围非常困惑觉得2这种边界很难记。建议你直接代入数字验证n 4, k 2当 path 为空时len(path) 0range 的上界是 4 - 2 2 4所以 i 可以取 1、2、3、4当 path [1] 时len(path) 1上界是 4 - 1 2 5但 range 本身会截断到 4所以 i 最多取到 4正好够选第二个数。这么验一次之后边界就不会再错了。2.3 为什么必须用 path[:] 而不是 path这里有一个百分之九十九的初学者都踩过的坑收集答案时写成了res.append(path)。表面上看起来没问题但跑起来会发现结果全是空列表或者全部是同一个列表。原因是 path 是 Python 里的可变对象存进 res 的是它的引用而不是拷贝。后续递归继续 append 和 poppath 的内容一直在变之前存进 res 的那些“答案”也会跟着变最终所有答案都指向同一个最终状态。所以收集答案那一行必须写成res.append(path[:])用切片强制拷贝一份当前路径的快照。这个坑不只是组合题有所有回溯题都一样属于一次学会终身受用的教训。3. 组合总和LeetCode 39允许重复取数时的索引逻辑3.1 题目差异每个数字可以被无限次使用组合总和 I 的题目是给一个无重复元素的候选数组 candidates 和一个目标数 target找出所有和等于 target 的组合。candidates 中的数字可以被无限制重复选取。比如 candidates [2, 3, 6, 7]target 7答案就是[[2, 2, 3], [7]]。和 77 题相比最大的区别是同一个数字可以反复使用所以递归的时候不再传 i 1而是传 i 本身。这样就保证了下一层还能继续选当前这个数字。但“可以重复选”不代表“可以从头选”。如果某一次递归不小心传了 0从头开始那 [2, 3] 和 [3, 2] 就会同时出现在答案里组合就变成排列了。所以这里的核心约束是同一元素可以重复取但取数的方向只能向后不能回头。3.2 排序后剪枝才是真正的关键先看代码class Solution: def combinationSum(self, candidates: List[int], target: int) - List[List[int]]: res [] path [] candidates.sort() # 关键排序 def backtrack(start: int, remaining: int) - None: if remaining 0: res.append(path[:]) return for i in range(start, len(candidates)): # 剪枝candidates[i] 已经比剩余目标大后面的更大直接退出 if candidates[i] remaining: break path.append(candidates[i]) backtrack(i, remaining - candidates[i]) path.pop() backtrack(0, target) return res这里我用了remaining剩余目标值而不是每次都计算sum(path)。这个选择的理由很实际每次递归都去 sum 一次路径时间复杂度会额外多一层 O(k)而用一个整数做减法代价是 O(1)。排序 break 的组合是这道题剪枝的核心。因为数组是升序的一旦发现当前candidates[i] remaining说明后面的数字更大全都大于 remaining这一整层都不可能有答案了直接 break 跳出循环即可。如果不排序就只能用 continue虽然也能找到答案但会白白遍历完整个数组才知道后面没有可行解。3.3 用 2、3、6、7 完整走一遍流程以 target 7 为例演示一下递归路径第一层 start 0i 0选 2remaining 变为 5第二层 start 仍为 0i 0再选 2remaining 变为 3第三层再选 2remaining 变成 1此时 2 1 触发 break递归返回撤销到 remaining 3 的状态第三层继续 i 1选 3remaining 正好归零收集答案 [2, 2, 3]继续回退探索其他分支最终找到 [7]。你注意看第三层选 3 时递归函数是带着上一层的 i 0 进去的所以循环仍然从 0 开始枚举这才保证了 2 能被反复使用。而一旦到某一层选了 3下一层的起点就是 i 1只能选 3、6、7不能回头选 2也就不会再出现 [3, 2, 2] 这种重复组合了。这里建议你自己动手画一遍递归树比看任何解释都管用。画的时候重点看 start 参数是怎么一层层变化的你就彻底明白为什么“能重复但不能回头”。4. 组合总和ⅡLeetCode 40排序后同层去重的判断时机4.1 有重复元素时最怕的是同一层出现两个一模一样的数字组合总和 II 比 I 多了一个限制candidates 里可能包含重复元素但每个元素只能用一次而且最终答案不允许包含重复组合。典型的例子candidates [10, 1, 2, 7, 6, 1, 5]target 8。如果直接套用组合总和 I 的逻辑会得到两组 [1, 7] 和 [1, 7]因为数组里有两个 1。去重的核心思路是先把数组排序让相同的数字挨在一起然后规定在递归树的同一层如果一个数字和前一个数字相同那它就跳过。为什么是“同一层”而不是“所有位置”因为 [1, 1, 6] 这种组合里两个 1 分别来自数组中不同位置的同一个数但它们不在递归树的同一层是合法的不能去重。4.2 两种主流去重写法i start 与 used 数组先看最常见的写法用i start判断同层重复class Solution: def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]: res [] path [] candidates.sort() def backtrack(start: int, remaining: int) - None: if remaining 0: res.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] remaining: break # 同层去重当前数字和前一个数字相同且不在本层第一个位置 if i start and candidates[i] candidates[i - 1]: continue path.append(candidates[i]) backtrack(i 1, remaining - candidates[i]) # 每个元素只能用一次 path.pop() backtrack(0, target) return res为什么是i start而不是i 0因为i 0会把跨层重复也去掉比如 [1, 1, 6] 这种本身合法的组合会被误杀。i start的含义是只有当当前元素是本层循环的第二个及以后的位置时才检查和前一个元素是否相同。如果相同说明前一个相同数字已经在更早的递归分支中处理过同样的情况了当前这个分支产生的组合必然是重复的。另一种写法是用 used 数组记录元素是否被用过class Solution: def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]: res [] path [] used [False] * len(candidates) candidates.sort() def backtrack(start: int, remaining: int) - None: if remaining 0: res.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] remaining: break # 前一个相同数字未被使用说明当前是在同一层重复枚举 if i 0 and candidates[i] candidates[i - 1] and not used[i - 1]: continue used[i] True path.append(candidates[i]) backtrack(i 1, remaining - candidates[i]) path.pop() used[i] False backtrack(0, target) return resused 数组的写法和排列问题的习惯一脉相承。在这个场景里not used[i - 1]的效果和i start是等价的前一个相同数字没有被用说明当前层是从它之后开始的也就是它在同一层的更靠前位置已经被选过了当前这个分支属于重复枚举。4.3 一个让很多人懵掉的细节跨层的相同数字不能去重我还是想再用一个具体的例子把“同层 vs 跨层”说透。假设排序后的数组是 [1, 1, 2, 5, 6, 7, 10]target 8。正确答案里有一个组合是 [1, 1, 6]。这个组合里两个 1 来自数组下标 0 和 1它们在递归树上的位置分别是第一层和第三层中间隔了选择第二个 1 这一层属于不同层所以不能去掉。如果去重条件不小心写成了if i 0 and candidates[i] candidates[i - 1]那么当递归走到第二层选第二个 1 时因为前一个是 1 且已经被使用这个条件永远不触发问题不大但当它试图在同一层枚举第二个 1 时条件会拦住它。可真正的灾难是某些变种题里如果逻辑写反了会把 [1, 1, 6] 这种合法答案也过滤掉。所以判断去重条件时脑子里一定要有一棵递归树问自己“我现在是在树的哪一层这个重复元素是我在本层第二次遇到还是沿着路径深入后遇到的”5. 剪枝的性价比排序时机、提前终止与复杂度对比5.1 排序到底改变了什么组合总和 I 和 II 里第一件事就是对 candidates 排序。很多人不理解排序本身是 O(n log n) 的开销到底值不值答案是在包含剪枝的回溯里排序带来的收益远超这点开销。因为剪枝能让大量分支在很浅的层次就被终止而一旦 candidate 大于 remaining当前层以及后面所有更大的元素都不用再尝试了。如果数组长度很小比如不到 10排序与否感觉不出来但当 candidates 长度到几十、target 又比较大时剪枝带来的性能差距是指数级别的。我实际测试过一组数据candidates 长度 30target 300不排序、只用 continue 的版本跑了大概 4 秒排序 break 的版本不到 100 毫秒。刷题时这个差距就直接体现在超时和不超时之间。5.2 三道题的时间复杂度怎么看回溯算法的时间复杂度其实很难精确给出业界通用的表达方式是“叶子节点数 × 路径长度”。这里我给一个便于记忆的估算表题目递归树形态时间复杂度77. 组合每层选一个n 选 kO(C(n, k) * k)C(n,k) 是组合数39. 组合总和每个位置可重复选深度取决于 target / min(candidates)最坏 O(target^n) 级别剪枝后大幅下降40. 组合总和Ⅱ每个元素最多选一次最坏 O(2^n * n) 级别剪枝后大幅下降注意 39 题的理论复杂度是最差的因为可以无限重复选同一个数树的深度理论上可以达到 target 除以最小元素的值。实际解题时判断能否用回溯的标准很简单候选集大小是否在可接受的搜索空间内以及剪枝是否能显著减少无效分支。如果输入规模明显超出这个范围就该考虑动态规划或者贪心了。5.3 剪枝的三个层次从必做项到进阶项剪枝不是玄学它有明确的优先级。我自己总结成三个层次第一层必做基于约束条件的剪枝。比如剩下的和不够了、路径长度已经达到 k直接 return。这是回溯题的默认配置没有这层剪枝很多题都过不了。第二层强烈建议基于有序数组的提前终止。排序后一旦发现当前元素已经超出边界直接 break。这个在前面两题里已经体现得很明显。第三层进阶基于可行性预判的剪枝。比如路径中已有的最大元素、剩余可选的元素个数等能够提前算出“这条路即使走到最深也达不到目标”就可以在进入循环前拦截。77 题的n - (k - len(path)) 1就是这一层的小型实践。记住一个原则剪枝是在保证不漏解的前提下减少无效计算千万不要为了剪枝而误杀正确答案。写完剪枝后最好用几组边界数据把结果核对一遍。6. 实战排错四个最容易写崩的地方与调试方法6.1 忘记撤销选择路径被“污染”这是出现频率最高的错误。递归返回后没有执行path.pop()导致下一轮循环时 path 里残留着上一个分支的元素。表现是第一组答案正常后面所有答案都莫名其妙地多出一堆数字。解决办法是养成口诀式的习惯append 和 pop 必须成对出现且中间只隔一次递归调用。你也可以在写代码时有意识地数一下“对称性”如果path.append(i)在第 10 行那么第 12 行递归第 13 行一定是path.pop()。6.2 res.append(path) 存储了引用而不是快照这个前面已经提过。记得使用path[:]而不是path本身。如果你发现最终结果里所有子列表都一样或者全部是空列表第一个检查点就应该放在这里。用 Python 刷题的同学尤其要小心这一点。Java 刷题时同样要注意更安全的做法是new ArrayList(path)不要直接res.add(path)。6.3 去重条件写错层级组合总和 II 的去重条件必须是i start不是i 0。一旦写错合法的深层次组合会被误杀。我自己见过同学把i start写成i 0之后[1, 1, 6] 这种答案永远出不来卡了半个小时没找到原因。如果你发现自己少了某些看起来合法的组合优先检查去重条件是不是影响了跨层选择。6.4 调试工具打印递归树很多人遇到回溯题结果不对只知道干瞪眼看代码。我强烈建议你在本地调试时临时加一行打印把递归层级、当前 start、当前 path、remaining 全部打出来def backtrack(start: int, remaining: int, depth: int) - None: print( * depth fstart{start} path{path} remaining{remaining}) ... backtrack(i 1, remaining - candidates[i], depth 1)运行完你会得到一颗完整的递归树输出。对照题目手画的那棵树很快就能定位到底是哪一层逻辑出了问题。调试完记得把打印删掉或者用注释控制别让线上代码带着一堆调试输出。6.5 关于“在 no command 界面调用隐藏 recovery 菜单”这类话题的提醒有时候刷题刷到一半会遇到一些奇怪的网络搜索词比如“在 no command 界面执行组合操作调出 recovery 菜单”之类的系统操作描述。这和回溯算法本身没什么关系可能是搜索时误触了其他主题。如果你真的在调试设备时遇到这类需求请务必以官方文档、品牌官网和正规技术社区的内容为准不要轻信来路不明的命令行操作指引。没有可靠的来源验证前不要对设备执行任何修改类操作。写算法题把精力集中在递归与剪枝的思路上就好。7. 三种组合类题目的对比与变种迁移思路7.1 三题核心差异一表看懂我把三道题的核心差异整理成一张表方便你随时翻出来对照维度77. 组合39. 组合总和40. 组合总和Ⅱ元素能否重复使用不重复可无限重复每个最多一次原数组是否有重复无1..n 天然去重无重复有重复递归起点参数i 1ii 1去重处理不需要不需要排序 同层跳过结束条件len(path) kremaining 0remaining 0你会发现递归起点参数其实就由“元素能否重复使用”决定能用 i不能用 i 1。而去重处理只由“原数组是否有重复”决定有重复就必须排序后做同层去重。这两个判断打通之后组合类问题就不会再出错了。7.2 变种题怎么套很多面试题看起来花样百出本质上都是这三道的变体。比如子集问题78. 子集相当于 k 从 0 到 n 的所有组合的并集只需要在每次递归进入时都收集答案即可。电话号码的字母组合17 题candidates 换成了字母串但框架完全一致只是每次递归的可选列表来自当前数字对应的字母集合。复原 IP 地址93 题本质上也是组合问题只不过每段长度有限制剪枝条件变成了“当前截取的数字段是否合法”。遇到任何组合类变种你先问三个问题元素能重复吗原数组有重复吗收集答案的条件是什么三个问题回答完代码框架基本就出来了。7.3 实战中的性能调优提前排序 剪枝一个容易忽略的细节是如果题目要求返回结果按字典序排列那么排序候选数组本身就能让回溯天然地按字典序生成答案省去最后排序的额外开销。比如 40 题candidates 排序后回溯产生的组合就是字典序这也算排序剪枝的“隐藏福利”。另外如果递归函数里没有需要保留的上下文状态Python 里可以把递归函数定义在 Solution 方法内部用闭包共享 res 和 path省去每层传递参数的噪音。这在写代码时能显著提高可读性也方便直接把 path 打出来调试。写到这里三题和一整套回溯框架的来龙去脉已经梳理完了。我个人在实战里最大的体会是回溯题不怕不会写就怕你会写但不知道为什么能对。每当你写下一行代码都试着问自己“删掉它会怎么样”。比如删掉 start 参数会变排列删掉排序会变慢删掉 pop 会让答案错乱。多问自己几个为什么把这三道题彻底内化成自己的肌肉记忆之后遇到任何回溯的变种题你都能在十分钟内搭建出正确的框架剩下的无非是在剪枝条件上做文章。