回溯算法从原理到剪枝：掌握递归+撤销，吃透组合问题

回溯算法第一次遇到的时候大多数人都会觉得有点绕。代码随想录里把它安排在二叉树之后、贪心之前其实是有讲究的——你只要掌握了递归回溯基本就是“递归加撤销”的套壳玩法。这篇笔记我会把day22的内容拆开揉碎从基本原理、代码模板到LeetCode上的经典题目尽量把每个细节讲透尤其是剪枝那步多数人第一遍要么背不下来要么不知道它为什么省时间。文章适合刚刷完二叉树、准备啃回溯的读者也适合学了一遍但总觉得哪里没通的人。1. 回溯算法到底在解什么题1.1 一眼认出回溯题的四个特征拿到一道题先别急着想递归怎么写先判断它是不是回溯题。我的经验是只要题目同时满足下面这几条基本就是回溯的场子问的是所有组合、所有排列、所有子集而不是最优解。它不问你“最短路径是多少”而是“把所有可能的路径都列出来”。每一步的选择都来自一个集合而且做过的选择通常不能再选组合、排列都常见。解的结构是树形的每一个分支就是一条候选路径。终止条件不是递归到空而是收集到了满足长度的结果或者超出了可选范围。比如组合问题“从n个数里选k个数”它要的是所有组合切割问题“把字符串切成若干回文子串”它要的是所有切法棋盘问题“n皇后”要的是所有摆法。这些题的共同点就是穷举所有可能性而回溯就是干这件事的标准工具。1.2 为什么回溯天然要用递归实现很多人第一次看回溯代码会觉得函数里套着for循环、for循环里又递归调用自己结构很别扭。其实你换个角度理解就不别扭了for循环管的是同一层往右走递归管的是往下一层深挖。用生活里的场景类比你在一个迷宫里找出口每条路走到尽头如果是死路就退回岔路口换下一条路继续走。这个“往下走”的动作就是递归“退回岔路口”的动作就是撤销也就是回溯名字的由来。所以要想实现“走完这条再看看那条”的效果递归是天然匹配的——递归自带函数栈上一层没干完的事全存在栈里退回时自动恢复现场。理解了这一点你就能看懂回溯代码为什么是“同一个函数里套着一个for循环for循环里又调用自己”了。而代码随想录里总结的“回溯三部曲”本质上就是把递归三要素套到了一个更具体的搜索场景上。2. 回溯算法的核心框架与原理拆解2.1 回溯三部曲参数、终止条件、单层搜索代码随想录把回溯写法总结成了三步我建议你就按这个顺序写思路不容易乱。第一部确定递归函数参数。回溯函数的参数通常包括结果集用来装最终答案、单条路径用来装当前探索到的分支、决策的起始下标这个特别关键后面会详细讲、以及题目给的原始输入。因为回溯通常是全局搜索路径和结果集往往放在类成员变量里函数参数尽量精简你只需要保证递归调用时能“选中哪些选项”就行。第二部确定终止条件。终止条件往往就是路径长度够了或者当前路径满足题意。比如组合题当path.size()等于k时就把path加入结果集然后return。注意这里return完不是整个函数结束而是结束这一层递归回到上一层继续找下一种组合。第三部确定单层搜索逻辑。这是回溯函数的主体套路非常固定从startIndex开始遍历可选集合。把当前元素加入path。递归调用自己传入i1作为下一层的startIndex。递归返回后把刚加进去的元素移出path。这个“加入-递归-撤销”三步走就是回溯的核心循环。你把这套骨架背下来很多题都能套上去改改条件就行。2.2 用树形结构理解回溯的宽度与深度学回溯一定要画树。不画树单靠脑子想代码一乱就迷。树的结构是这样定义的树的每一层对应一个递归层级也就是“已经选了几个数”的状态。每一个树枝对应一个可能的选法。叶子节点就是满足终止条件的完整路径也就是我们要收集的答案。宽度是指一层里面有多个可选分支这个来自for循环深度是指从上往下一直走到叶子这个来自递归调用。for循环和递归一配合所有组合就像在树上做了一次深度优先遍历每个叶子代表一种完整结果而回溯只是在这个遍历过程中把不符合要求的分支剪掉或者走到头之后原路返回换个分支再走。2.3 撤销操作的必要性为什么大家都在强调这一步代码里最容易被忽略、又最不能省的一行就是path.pop_back()。我见过不少小白把这一行删了结果输出全是同一个重复的组合。原因很简单path是一个共享变量它贯穿整个递归过程。假如你不撤销递归回到上一层之后path里还留着下一层加进去的元素那你下一轮for循环一开始path就不是“上一层状态新元素”而是“上一层状态旧的下层元素新元素”路径长度瞬间就错了而且你还会发现结果集里所有答案的长度对不上。打个比方你在试卷上用铅笔写答案每完成一道题你就要把草稿擦掉再写下一道。如果不擦草稿就混进了正式答案。撤销就是在“交卷”之后把草稿擦掉好让下一轮从干净的起点开始。另外要注意撤销的位置很有讲究。只能发生在递归调用返回之后不能放在递归调用之前也不能在终止条件里顺手撤销。你得想清楚递归回来后代表这个分支已经探索完这时才轮到当前层撤销上一个选择让for循环继续尝试下一个选择。3. 实战拆解LeetCode 77 组合问题完整解法3.1 题目的本质n选k且顺序不关心题目描述很简单给定n和k返回1到n中所有可能的k个数的组合。比如n4k2那答案就是[1,2]、[1,3]、[1,4]、[2,3]、[2,4]、[3,4]。注意[2,1]和[1,2]是同一个组合不能重复。很多初学者会直接用嵌套for循环来想这个问题。k2时双层循环确实能解但如果k是变量就不可能有k层循环写在代码里。这就是回溯登场的原因它用递归的动态深度代替了静态的循环层数k是多少递归就落多少层。这个题也是代码随想录day22的开胃菜别看它简单前面讲的一套框架在这道题里全都能落地。3.2 先写一个不剪枝版本跑通逻辑不急着优化先把最直观的版本写出来。代码如下class Solution { private: vectorvectorint result; vectorint path; void backtrack(int n, int k, int startIndex) { if (path.size() k) { // 终止条件路径长度够了 result.push_back(path); return; } for (int i startIndex; i n; i) { // 从 startIndex 开始选 path.push_back(i); // 做出选择 backtrack(n, k, i 1); // 递归下一层不能重复选取 path.pop_back(); // 撤销选择 } } public: vectorvectorint combine(int n, int k) { result.clear(); path.clear(); backtrack(n, k, 1); return result; } };我们来模拟一下n4、k2时第一层i1发生了什么第一层选1path变成[1]递归进入第二层第二层startIndex2。第二层i2path变成[1,2]此时path.size()2收集答案[1,2]return。回到第二层for循环的下一轮i3path要先恢复成[1]因为上一轮递归返回后执行了pop_back再加入3收集[1,3]。同理收集[1,4]第二层遍历完返回第一层。第一层也执行pop_backpath变回空然后i2开始以2开头的所有组合。这个过程看着简单但你可能注意到一个关键点每次递归返回后path会被pop_back一次然后for循环继续走。所以path的长度在任意时刻都等于当前递归层数这就是撤销操作保持的数据不变量。3.3 剪枝优化为什么是 n - (k - path.size()) 1不剪枝版本对n100、k50这种输入效率会有点难看。因为有很多分支根本凑不满k个数却还要递归好几层才发现浪费大量时间。剪枝的思路很简单如果当前剩余的可选数已经不够凑满k个了那就别继续了。什么情况下剩余可选数不够假设当前已经选了path.size()个还需要选rest k - path.size()个。而当前从startIndex开始到n为止最多能选几个数n - startIndex 1个。如果这个数小于rest说明无论如何都凑不满k个直接终止这一层循环。但代码随想录里的写法更精妙它不判断“还能选多少”而是限制for循环的终点for (int i startIndex; i n - (k - path.size()) 1; i)这个终点的意思是确保i以及它后面的数加在一起足够再凑出剩余所需的元素个数。举个例子n4k3当前path为空rest3。i最多能到4-312。也就是说第一层i最多选到2因为如果i取3后面只剩一个数4一共才2个数不可能凑满3个。画出树你就能看到那些取3、4开头的分支全是死枝剪掉完全不心疼。我记得第一次看这个表达式也有点蒙后来用具体数字代入才明白。你可以拿笔算一遍当前选了0个k3n4终点 4 - 3 1 2i最大取2。当前选了1个k3n4path.size()1rest2终点 4 - 2 1 3i最大取3。这是在第二层因为第一个选了1后面还能选两个数最多能选到3即1,3,4如果选第四个则凑不满。这个常数级别的改动能把很多无效分支在很浅的层就砍掉尤其当n远大于k时效果肉眼可见。3.4 延伸题组合总和III与电话号码的字母组合组合总和III216题和77题的框架几乎一模一样。题目改成只允许使用1到9的数字每个组合不能重复且各数字之和等于目标n。你只需要在77题的终止条件那里多判断一个sum是否等于n或者提前用sum做一次小剪枝。这种题做多了你会发现回溯就是“模板改条件”的活。电话号码的字母组合17题稍微变了一点它是多棵树上同时搜索不是从单一数字集合里选。它需要你先根据digits字符串逐位取出该数字对应的字母组然后这一层for循环遍历的集合就是这个字母组。这里startIndex不能简单传i1而是传index1因为每一层对应的是digits里的一个位置而不是同一个集合里的不同起点。第一次接触这个差异时容易绕但它其实只是“每层可选集合不同”的回溯变种。4. 回溯的时间复杂度与空间复杂度分析4.1 为什么回溯是指数级复杂度回溯本质是穷举所以它的时间复杂度通常很高——这听起来不像个好算法但它的存在意义恰恰在于在面对没有更优解法的问题时给一个思路清晰、一定能搜到结果的方案。以组合题为例从n个数里选k个组合总数是C(n, k)时间复杂度是O(C(n, k))。而每个组合在收集时还要把path复制进result这个复制本身的成本是O(k)所以严格说是O(k * C(n, k))。对n20、k10这个数字已经上亿量级了所以剪枝才这么重要——它不能改变指数级的下界但能砍掉大量无效空间。排列问题更夸张n个数的全排列是n!n10就是3628800n15就是13亿。所以回溯题在面试中n的规模通常都比较小一般在20以下。如果看到n特别大那大概率不是用回溯硬解要么有更巧的数学或动态规划解法要么题目本身就是要你用回溯但限制数据范围。4.2 空间复杂度递归栈到底占多大空间复杂度主要来自两部分。一是递归调用栈。回溯的递归深度等于树的深度组合题的深度就是k所以这部分是O(k)。如果是排列题深度是n所以是O(n)。二是path向量本身存储当前路径最长也是O(k)或O(n)。当然result里保存的所有答案不算在算法空间复杂度里——不过真实场景中如果你把result当成员变量一直保存它会占很多内存。理论上讲这是输出本身需要的空间一般不计入算法空间复杂度但面试时最好主动提一句显得你考虑全面。4.3 回溯、递归、DFS三者的关系搞清楚这三个概念经常混着用很多人在day22这里彻底分不清了。我用自己的理解给你捋一下递归是一种函数调用自身的编程技巧它是回溯的实现载体。DFS深度优先搜索是一种遍历算法专注于“深度优先”地探索节点。回溯算法在搜索过程中采用的正是DFS的遍历顺序。回溯是一种解决问题的策略它用DFS的方式探索解空间树当发现当前分支一定无解或已经得到一个解时撤销这次选择退回上一层换一个分支继续。所以三者的关系大概是回溯算法是一种DFS而递归是写回溯时用的工具。换句话说每一道回溯题都天然带着一棵解空间树你的代码在树上的遍历方式就是DFS。理解这个关系有个实际好处以后看到“n皇后”“单词搜索”这类题你可以直接用DFS的思维去想只不过多了一个“撤销”的操作。本质上它们是一家人。5. 新手常见坑与排查技巧实录5.1 坑一startIndex传错结果全是重复组合我见到的第一个高频bug就是递归调用时写了backtrack(n, k, startIndex)而不是backtrack(n, k, i 1)。这会导致下一层又从同一个起点开始选输出里全是重复组合。为什么必须是i1因为当前已经选了i这个数下一层为了避免重复只能从i的下一个位置开始选。startIndex传的是“这一层可以从哪里开始选”而它由上一层选择了哪个元素决定所以必须用循环变量i来更新。你可以想成一个下标指针每往下走一层指针就向右挪一格防止回头。5.2 坑二撤销的位置写错或漏写前面说过撤销必须紧跟在递归调用返回之后。我见过有人把pop_back写在递归调用之前意思变成“先撤销再递归”那样path在递归时就少了一个元素还有人把pop_back写在终止条件里会导致结果集收到错误状态。最快的判断方法如果调试时发现path长度忽长忽短或者结果集长度不对十有八九是撤销位置的问题。你可以在for循环的开头打一行日志打印当前path的状态立刻就能看到哪里多删了或多加了。5.3 坑三剪枝条件写反导致结果缺失剪枝写错有两种典型情况一是把终点算小了导致有些合法组合根本没被遍历到二是把剪枝条件放在循环内部用continue跳过而不是直接结束循环白白增加判断次数。稳妥的做法是先写不剪枝版本确保逻辑正确、答案全对再就地对for循环边界做小改动。不要一上来就把剪枝和回溯逻辑混在一起写那样出了问题很难定位到底是谁的锅。我常用的调试方法是打印每一层递归进入时的startIndex和path对照着树形图看哪一步和预期不一致就能快速锁定问题。5.4 回溯问题快速排查速查表这里把day22阶段最常见的几个问题整理成一张表现象可能原因解决思路结果重复递归传了startIndex而不是i1改成传入i1避免回头选答案长度不对撤销遗漏或位置错误检查pop_back是否紧跟递归返回缺少部分答案剪枝终点算小了回退到不剪枝版本核对遍历范围出现空结果终止条件优先级不对确认先在path.size()k时收集并return全排列多出重复项没有用used数组去重像电话号码这题要用下标排列题常用布尔数组标记已选5.5 刷题阶段的一个小建议先画树再写代码最后分享一个我自己的习惯也算是在回溯学习阶段最大的经验。拿到回溯题第一件事不是想代码而是在纸上画出它的解空间树哪怕只是画三四个节点的前两层。树画出来了递归层数、for循环范围、终止条件、撤销位置全都一目了然。代码很多时候是照着树“翻译”出来的而不是硬憋出来的。我现在刷回溯题依然习惯先在草稿纸上写“startIndex、path、终止条件”三个变量名然后推演一遍递归过程再动键盘。这个方法对组合、切割、子集、排列这四类题都适用。等你练多了就会发现回溯题虽然长得五花八门但底层的树形结构是相通的。掌握好一棵树的遍历剩下的都是变形。代码随想录day22只是开了个头后面的子集、排列、棋盘问题全都在这个框架上做加法。把组合题吃透后面会顺很多。