刷算法题这件事我见过太多人卡在同一个地方一道“组合总和”看答案只有十几行真轮到自己写却总在递归里绕晕。问题通常不是递归本身而是没弄明白回溯那一整套“选进去、递归、退出来”的循环机制。追溯起来回溯算法最经典的入门场景就是组合与组合总和这一串题目几乎就是整个回溯体系的“最小可复现单元”。搞懂了它后面再遇到子集、全排列、棋盘、岛屿类问题基本都是套模板加改条件的事。这篇文章我就把回溯算法里最核心的组合类问题从原理到模板、从剪枝到去重完整地过一遍。不管你是刚开始刷题的新手还是被去重逻辑折磨过的老手应该都能从这里捞到一些能直接上手的东西。1. 回溯算法到底在做什么组合问题的第一性原理解析1.1 组合问题为什么是回溯算法的“标准入门题”先明确一个基本概念组合和排列不一样。排列在乎顺序组合不在乎顺序。从[1,2,3]里选两个数按排列算是[1,2]和[2,1]两种按组合算就只有[1,2]一种。很多初学者写回溯会写出重复结果根本原因就是把组合当排列写了没有在代码里体现“不回头”的约束。回溯算法解决的就是这类“从多个选项里不断选择直到满足某个目标”的枚举问题。你可以把它想成在岔路口做选择选了某条分支往前走发现走不通或者已经收集完一个答案就退回到上一个路口换另一条分支继续试。这个“退回”的动作就是“回溯”对应到代码里就是递归之后的path.pop()。组合问题之所以是回溯的标准入门题是因为它的状态非常干净每一层只需要考虑“从当前位置往后选哪些数”不需要处理棋盘约束、图搜索、复杂的状态重置。它保留了回溯最核心的“选择-递归-撤销”链路又剔除了大量干扰信息最适合用来建立直觉。如果你直接上手全排列或者N皇后很容易被各种附加规则分散注意力反而不容易抓住回溯的骨架。我见过不少同学先刷了N皇后才回头补组合题回头跟人说“回溯好难”其实顺序反了组合题才是那个“电梯入口”。1.2 回溯三要素与代码通用骨架写回溯题我习惯先想清楚三个东西几乎所有的回溯题都可以用这三件套拆解路径path记录已经做出的选择也就是当前这条分支上收集的临时答案。选择列表startIndex / candidates当前这一步可以尝试哪些选项还剩哪些可选。结束条件什么时候把path里的内容记入最终结果。通用骨架长这样result [] path [] def backtrack(参数): if 满足结束条件: result.append(path[:]) return for 选择 in 可选项: 做选择 backtrack(新的参数) 撤销选择 return这个骨架几乎是所有回溯题的母版。难的地方在于“参数怎么传”和“怎么做选择才不会重复”后面我会一个一个展开。这里有一个很容易埋雷的细节记录答案时一定要用path[:]而不是path。Python里的path是同一个列表对象的引用如果不做拷贝后面所有递归分支修改的都是同一个列表最终result里存的会全部变成最后清空的状态。我见过太多人在这一步吃大亏明明逻辑全对最后输出的结果却是一堆空数组。用path[:]或者list(path)做一份快照才能保住当前分支的答案。这个坑我在第4章还会再强调一次因为它出现的频率实在太高了。2. 从最基础的组合题开始组合的模板化写法2.1 LeetCode 77 组合完整代码与执行过程剖析先说最基础的组合题给定数字范围1到n返回所有k个数的组合组合内数字不重复。这是回溯模板的“Hello World”。代码如下Python版本def combine(n: int, k: int) - List[List[int]]: res [] path [] def backtrack(start: int) - None: if len(path) k: res.append(path[:]) return for i in range(start, n 1): path.append(i) backtrack(i 1) path.pop() backtrack(1) return res用n4, k2手动推一遍你会看得非常清楚调用backtrack(1)for i in range(1, 5)先走到i1path变成[1]然后递归backtrack(2)。在backtrack(2)里i从2开始path[1,2]长度达到2记录[1,2]并返回。返回后pop()掉2接着backtrack(2)的循环里i3得到[1,3]同理得到[1,4]。最外层i2时path[2]递归backtrack(3)依次得到[2,3]、[2,4]。i3时得到[3,4]。注意观察每次递归传入的start都是上一轮选的数加1。这正是组合不重复的关键通过startIndex强制“只能往右选”从源头上杜绝了[2,1]这种排列型结果。2.2 startIndex 这个参数为什么必须存在如果你之前写过全排列会知道全排列用used数组来标记哪些元素用过了不需要startIndex。因为排列允许[1,2]和[2,1]同时存在每一层都能从头开始选而组合不允许必须通过startIndex把可选范围限制在“当前元素之后”。可以把startIndex理解成一个单向通道每次递归进入下一层时可选择的范围都被收缩了。这样做的好处不只是省代码更重要的是让搜索树从全排列的“全连接图”变成了组合的“上三角结构”搜索空间大幅缩小。全排列n4时第一层有4个分支组合n4, k2时第一层也只有4个分支但第二层分支数会逐层递减不会出现对称重复。这里有个常见误区有人觉得start从0还是1开始只是细节问题。其实它在逻辑上决定的是“本轮可选范围”。如果你把backtrack(i 1)误写成backtrack(start)那就会出现同一个数被选两次的情况结果里立刻出现[1,1]这种错误。很多人在组合总和那类题里搞错“可重复”和“不可重复”的区别本质上就是没搞清楚startIndex 1和startIndex在递归调用里的含义差异。2.3 组合总和 III把约束条件写进递归参数里接下来是组合总和的入门版用1到9的数字选出k个数使它们的和等于n每个数字只能用一次。这道题在77题基础上多了一个约束总和必须恰好等于目标值。我推荐直接把它做成递归参数cur_sum传进去而不是每次都对path求和。原因很简单递归里对列表求和是O(k)的操作虽然k一般不大但把这个O(k)累加到每个节点上整套递归下来性能就会明显下降。维护一个cur_sum每加一个数就同步更新这是一种很常用的回溯优化习惯。def combinationSum3(k: int, n: int) - List[List[int]]: res [] path [] def backtrack(start: int, cur_sum: int) - None: if len(path) k: if cur_sum n: res.append(path[:]) return if cur_sum n: return for i in range(start, 10): path.append(i) backtrack(i 1, cur_sum i) path.pop() backtrack(1, 0) return res这里我提前加了一个判断cur_sum n时直接return。这一步其实就是最简单的剪枝题目要求数字都是正数后面再加只会更大没必要继续递归下去。这个“正数可剪枝”的特性在组合总和中会被放大成更高效的策略后面你会看到它的威力。3. 组合总和系列重复选取与去重问题的深入拆解3.1 组合总和可重复选取只改一行代码的底层逻辑LeetCode 39题是组合类问题的又一个分水岭给定一个无重复元素的数组candidates和一个目标数target找出candidates中可以使数字和等于target的所有组合而且candidates中的数字可以无限重复选取。和77题、216题相比最大的变化是“同一个数字可以用任意多次”。这个变化反映到代码上竟然只是把backtrack(i 1, ...)改成backtrack(i, ...)也就是下一层递归的start不再加1依然包含当前元素。请注意这里改的不是for循环的遍历范围而是递归传递的start。很多人在这道题上写错就是因为手动在for循环里加了“重复处理”的逻辑结果越搞越复杂。其实回溯机制本身就照顾到了“重复”选完当前数字后下一层还能再选它就能实现无限次使用而start不往左回退又保证了组合内相对顺序稳定不会出现[2,2,3]和[3,2,2]这种重复组合。def combinationSum(candidates: List[int], target: int) - List[List[int]]: res [] path [] candidates.sort() def backtrack(start: int, cur_sum: int) - None: if cur_sum target: res.append(path[:]) return if cur_sum target: return for i in range(start, len(candidates)): if cur_sum candidates[i] target: break path.append(candidates[i]) backtrack(i, cur_sum candidates[i]) path.pop() backtrack(0, 0) return res另一个细节是我先把candidates排序了然后在for循环里加了if cur_sum candidates[i] target: break。排序配合break是这类“元素可重复使用且全为正数”的题目的终极剪枝因为已经排序一旦当前元素加上去超过target后面更大的元素也一定超过整个循环都可以直接放弃。这个优化看起来不起眼实际能把大量无效递归直接砍掉。我在本地测过candidates[2,3,5,7], target100这种规模有排序剪枝和无剪枝的耗时差距非常明显。3.2 组合总和 II排序used数组实现树层去重LeetCode 40题比39题又难了一步candidates里可能有重复数字而且每个数字在每个组合中只能使用一次。这就引入了回溯里最经典、也最容易让新人懵掉的“去重”问题。先给出结论重复数字会造成两种“重”一种是同一条分支内部重复使用同一个数字叫树枝重复一种是不同分支产生相同的组合叫树层重复。组合总和II要处理的是后者。比如candidates[1,1,2,3], target4如果不去重会得到多个[1,3]因为第一个1和第二个1分别都能构造出[1,3]。最常见的去重写法是配合排序使用一个used布尔数组def combinationSum2(candidates: List[int], target: int) - List[List[int]]: res [] path [] candidates.sort() used [False] * len(candidates) def backtrack(start: int, cur_sum: int) - None: if cur_sum target: res.append(path[:]) return if cur_sum target: return for i in range(start, len(candidates)): if i 0 and candidates[i] candidates[i - 1] and not used[i - 1]: continue if cur_sum candidates[i] target: break used[i] True path.append(candidates[i]) backtrack(i 1, cur_sum candidates[i]) path.pop() used[i] False backtrack(0, 0) return res这个candidates[i] candidates[i - 1] and not used[i - 1]到底是什么含义拆开看candidates[i] candidates[i - 1]说明当前数字和前一个数字值相同not used[i - 1]说明前一个相同值的数字在当前这一层没有被使用过它是上一个递归分支已经处理完并撤销掉的数字。此时如果再把当前数字选进来就会产生和“前一个数字在上一层被选”完全相同的组合。换句话说相同值的数字在同一层只允许第一个出现后面的兄弟分支全部跳过。而used[i - 1]为True时说明这是在同一条递归路径内正常使用的重复值比如[1,1,2]里两个1一起被选这种情况不能跳过否则会漏掉合法组合。如果不引入used数组其实还有更简洁的写法def combinationSum2(candidates: List[int], target: int) - List[List[int]]: res [] path [] candidates.sort() def backtrack(start: int, cur_sum: int) - None: if cur_sum target: res.append(path[:]) return if cur_sum target: return for i in range(start, len(candidates)): if i start and candidates[i] candidates[i - 1]: continue if cur_sum candidates[i] target: break path.append(candidates[i]) backtrack(i 1, cur_sum candidates[i]) path.pop() backtrack(0, 0) return res这个写法的原理是在同一个for循环内跳过那些和前一个元素值相同的位置因为前一个相同值的元素已经作为起点生成过整个子树了。用i start而不是i 0是为了保留树枝上的合法重复当递归进入下一层start变成了i 1此时如果下一层第一个元素和上一层选的元素值相同仍然可以被正常选用因为i start不会被跳过。这就是两个版本写法上最本质的差异。就我个人而言更推荐先用used数组版本理解原理再用i start版本去写代码。因为前者概念清晰能帮你分清树层去重和树枝去重后者代码更短适合面试时快速输出。3.3 剪枝优化从能跑到跑得快的两种剪枝策略到这里组合类回溯题的基本框架已经完整了。我总结一下这几种剪枝策略它们不是可有可无的细节而是回溯从“能跑”到“跑得快”的关键可行性剪枝cur_sum target或len(path) k时直接返回不再往下搜。这是最简单也最常用的一类剪枝几乎所有组合类题目都用得到。排序剪枝先给数组排序一旦cur_sum candidates[i] target就break退出循环因为后面的元素必然更大没有必要继续遍历。结构剪枝像77题里如果当前剩余可选数字已经不够填满path到k就可以提前返回比如n - start 1 k - len(path)时直接return。第三种结构剪枝很多人会忽略。举个例子n4, k3当递归到start3时path长度只有1剩下的数只有3和4最多能凑到2个数永远不可能凑满3个这种分支纯属浪费时间。在递归开头加上剩余数量判断就能砍掉一整片子树。这三类剪枝叠加起来搜索路径就从“盲目枚举”变成“带导向的探索”。在数据量稍大的时候差异非常明显。比如n20, k10这种规模不做剪枝的递归树会膨胀到难以想象的程度做完第一层剪枝后很多分支根本走不到底。回溯题在面试里被问多数时候不只看你会不会写模板更看你会不会在模板上叠加剪枝因为这才是工程里真正会遇到的性能问题。4. 回溯常见问题排查与实操心得4.1 五个高频坑点与解决方案速查我把刷题时自己和身边同事踩过的坑整理成一个速查表基本涵盖了回溯组合类的绝大多数问题症状原因解决方案结果里有[1,2]和[2,1]把组合当排列写了使用startIndex递归传i1或i不要从头开始选结果里出现[1,1]这种重复元素递归参数写成了startIndex而不是i1逐层检查递归调用时传入的start值最终答案全为空列表把path直接append进了result用path[:]拷贝后再append结果重复很多如多个[1,3]原数组有重复值且未去重排序后配合used数组或i start判断去重运行超时没有剪枝或剪枝条件太低效排序breakcur_sum提前判断剩余数量判断这个表是拿来应急的但真正要理解这些坑还是需要把上面几个代码示例亲手跑一遍。我见过一些同学把表抄下来背结果遇到变体题又不会了原因就是没有理解背后的递归结构。4.2 调试回溯代码的实战技巧调回溯题我有一个很笨但很有效的办法在递归入口打印path和当前start直接观察递归树。print( * len(path), fstart{start}, path{path})这样能直观地看到每一层循环从哪开始、选了什么、什么时候return。你很快就会发现回溯的递归过程不是线性的而是一层一层先深入到底再弹回来继续。理解了这种深度优先的节奏很多莫名其妙的bug就能一眼定位。比如有时候你觉得某条分支不该被遍历一打印就发现原来是start传错了导致本该死掉的分支还在跑。另一个技巧是边界值测试手动推n2, k1、n1, k1、target0、target小于最小值这些极端情况。回溯题的边界往往就是终止条件本身比如target0时应该返回空组合很多人在这种case上栽跟头。组合总和III还有一种特殊边界k0或n0这时候按要求应该返回[[]]还是[]取决于题目定义最好提前确认。还有一个习惯是小样例校验大逻辑先用最小的输入跑通再去验证大输入。我一般会在本地用n5, k3配合candidates[2,3,6,7], target7这种官方示例跑一遍确认结果数量和手算一致再提交到在线平台。手算能帮你建立直觉在线提交能帮你验证效率两者结合才稳妥。4.3 回溯的复杂度边界与实战选型建议回溯本质上是指数级别的枚举算法复杂度和搜索树的规模直接相关。以组合总和为例最坏情况下每个数字都可以被选多次递归深度最大是target / min(candidates)每个节点的分支数是len(candidates)所以最坏时间复杂度是指数级实际依赖剪枝效果。空间复杂度主要是递归栈深度和path长度组合题一般是O(target)或者O(n)。正因为回溯是指数级的它只适合处理小规模数据。n在20到30以内、需要枚举出具体方案的题目回溯是首选一旦输入规模到几百上千还想着用回溯硬解基本就是超时。这时候就该考虑动态规划、生成函数或者其他数学方法了。如果你看过机械工业出版社那本《组合数学原书第5版》会发现教材里更关心计数公式和生成函数而刷题时更多是需要把具体组合枚举出来这才是回溯的用武之地。至于实战选型我的建议很简单看到“返回所有组合”“求所有方案”这类字眼第一反应就是回溯模板如果题目只问“有多少种方案”而不是让列出具体组合那大概率可以用DP或者组合数学公式优化不一定非要回溯。这个判断在面试里非常加分能体现你对算法边界的理解而不只是背了一道题。最后分享一个我个人的习惯面试里写回溯题我不会直接闷头敲代码而是先跟面试官说“这道题我打算用回溯三要素是路径、选择范围和终止条件然后我会在递归里做两个剪枝”。这几句话一说面试官基本就知道你心里有底。单论回溯这个知识点最重要的一步其实是把模板背到肌肉记忆再通过组合总和这几道题把“什么时候改i什么时候改i1什么时候去重”这几个问题彻底理清楚。理清之后后面再碰子集、全排列、棋盘、岛屿类题目都会轻松不少。