1. 回溯算法的本质为什么它值得单独写一篇笔记学 C 到一定阶段很多人会卡在同一个坎上语法都会STL 也用得挺熟但一遇到求所有方案、枚举所有可能这类题就发懵。回溯算法就是迈过这个坎的第一道门。我在刚开始刷题那会儿看到全排列、子集、N 皇后这些题第一反应是写一堆嵌套循环结果题目规模一变就完全没法处理。后来才想明白回溯不是某种高深的技巧它就是把多层嵌套循环这件事交给递归去做同时在每一层做选择、做撤销让程序自己去走一棵决策树。这篇笔记面向的是已经能写基本 C 函数、懂递归但还没系统整理过回溯的同学。我会从模板讲起把它拆成路径、选择列表、结束条件三个部分然后拿子集、组合、排列、切割、N 皇后、数独这几类经典题型逐个过一遍。重点不在于背代码而在于搞清楚每一步为什么要这么写——比如为什么组合问题要传一个 start 索引而排列问题不用为什么去重要先排序为什么 N 皇后可以用三个标记数组把判重降到 O(1)。这些细节才是真正决定你能不能独立写出正确回溯代码的东西。我踩过的坑集中在几个地方一是传引用忘了回溯导致答案莫名其妙多出一堆元素二是去重逻辑写成结果集去重结果超时三是指数级复杂度没有剪枝跑小数据没事一上规模就爆。这些后面都会展开讲并且给出我实际用的排查方法。1.1 从暴力枚举到有剪枝的深度优先搜索很多人对回溯的直觉是暴力这个说法对了一半。回溯的骨架确实是把所有可能的解空间走一遍本质上是一棵深度优先搜索树。但真正让它能用的是剪枝——在走不下去的时候提前回头而不是傻乎乎地把整棵树遍历完。举个具体的例子。求 1 到 9 中所有长度为 5 的组合不考虑剪枝的话第一层循环从 1 到 9 都会展开但很明显如果你已经选了 8后面只剩 9 一个数凑不满 5 个这一支就没必要再走了。这种剩余元素数量不够的判断就是最常见的可行性剪枝。它把搜索树的一大块直接砍掉代码可能只多了一行if (n - i k - path.size()) break;但复杂度的常数能降一个量级。我的建议是先把不带剪枝的版本写对测试通过之后再回过头把剪枝加上用对拍的方式确认结果一致。这样调试起来心里有底不会出现加了剪枝结果错了但不知道错在哪的情况。1.2 回溯在 C 学习路线里的位置如果给 C 学习划一条线回溯大概处在语法与数据结构和算法思想之间的位置。往前的知识储备包括函数与递归、vector的增删改查、string拼接、引用与值传递的区别。这些不熟的话回溯代码写起来会处处别扭。往后的方向就多了。回溯是深度优先搜索的基础版本理解了决策树的遍历去看图论里的 DFS、去看记忆化搜索、去看动态规划的状态转移都会顺很多。尤其是记忆化搜索本质就是在回溯的搜索树上加了缓存如果你连搜索树长什么样都画不出来那部分内容基本没法真正吃透。所以我的判断是回溯值得花时间系统整理一遍而不是当八股背过就算了。在工程场景里回溯也不是只有刷题才有用。配置项的枚举校验、游戏里的走法生成、排班表在约束下的方案搜索、甚至某些构建工具里依赖顺序的合法排列推导底层都是同一套选择—探索—撤销的思路。只不过工程代码里更强调剪枝和提前终止因为真实数据的规模远比题目里的 n9 大得多。提示判断一道题要不要用回溯看两个信号——一是要求列出所有满足条件的方案二是数据规模不大但状态空间是组合爆炸的。两个信号都满足基本就是回溯的用武之地。2. 回溯的通用模板与三要素拆解刚接触回溯最容易被那种看起来能跑但说不清为什么的代码困住。我的做法是先建立一个固定框架把所有题目都往这个框架里套等套熟练了再去理解框架背后的灵活性。这个框架就是三个要素路径、选择列表、结束条件。路径是当前已经做出的选择序列通常用一个vector或者string承载。选择列表是当前这一步还能做哪些选择一般体现在 for 循环的范围内。结束条件是路径达到目标长度、或者走到了叶子节点这时候把路径存进结果集。三个要素对应到代码结构上就是进入函数先判断结束条件然后 for 循环遍历选择列表循环体内先做选择递归下一层再把选择撤销。2.1 路径、选择列表、结束条件路径这个概念要理解成从根节点到当前节点一路上的选择。以全排列为例选了 1、再选 3那么当前路径就是[1, 3]剩下的选择列表是[2, 4]。结束条件是路径长度等于数组长度说明所有位置都填满了。这里有个容易混淆的点选择列表并不是一个显式的数组多数时候它是由 for 循环的起点和 visited 标记共同决定的。比如组合问题靠 start 索引界定可选范围排列问题靠 used 数组标记哪些元素已被用掉。所以写代码时你不需要真的去构造一个剩余可选元素的数组而是用参数和标记把范围表达出来。结束条件的位置也有讲究。我习惯把它放在函数最开头先判断是否该收集结果再进循环。因为叶子节点也需要被收集如果放在循环里判断会漏掉最后一步。数独那种有唯一解、找到就可以返回的题结束条件还会配合返回值提前收工。2.2 标准模板代码与逐行注释下面这个模板我用了很久几乎所有回溯题都可以从它改出来void backtrack(参数) { if (满足结束条件) { result.push_back(path); // 收集一个合法方案 return; // 到达叶子回头 } for (选择 : 选择列表) { if (需要剪枝或跳过) continue; path.push_back(选择); // 做选择 backtrack(新的参数); // 进入下一层决策 path.pop_back(); // 撤销选择回到本层 } }逐行说一下。第一行结束条件注意result.push_back(path)存的是路径的副本如果用引用收集会出大问题后面排查部分会细讲。for 循环里的continue是剪枝和去重的入口。path.push_back和path.pop_back必须成对出现这是整个回溯最容易出错的地方只要有一处push_back没有对应的pop_back后面所有分支都会带着这个脏数据结果会变得非常离奇。递归调用的参数是最需要根据题目调整的部分。组合类问题通常传i 1作为新的起点表示下一个元素只能从当前之后选保证不重复排列类问题则不需要起点改用 used 数组标记。2.3 递归参数的设计取舍参数设计直接决定代码的简洁程度。我总结了一条经验能通过全局变量或成员变量表达的共享状态就不要一股脑塞进参数列表。比如结果集result、当前路径path、used 数组这些在递归过程中是共享的写成成员变量或者引用传参都行塞进参数里反而会让签名长到看不清。需要跟着每层变化的量才适合作为参数。最典型的就是 start 索引它随层数推进而增大是本层可选范围的直接体现。再比如数独里的行号 row、列号 col或者棋盘类问题里的坐标这些是每层独有的状态必须作为参数往下传。引用还是值传递也要想清楚。vector和string作为路径时一般用引用避免每层拷贝的开销但如果题目需要保留某一层的快照那就得传值。我早期吃过一次亏把路径按值传给下一层本意是想省掉 pop_back结果内存和时间都翻倍规模一上去直接超时。后来老老实实改回引用加手动撤销稳得多。3. 从子集到排列组合四类经典题型的写法差异题库里回溯的题看着五花八门归纳下来其实就四类子集、组合、排列、切割含棋盘。它们的模板高度相似差异集中在两个点上——选择列表怎么界定以及重复元素怎么处理。把这两个点吃透你会发现绝大多数题都能一眼看出改哪里。3.1 子集问题无重与有重无重复元素的子集最好写因为每个元素的状态只有选和不选且顺序无关。核心循环从 start 开始每次递归把当前路径收进结果集注意这里不需要等到叶子才收集因为任意长度的前缀都是一个合法子集。void dfs(vectorint nums, int start) { res.push_back(path); // 每个节点都是一个子集 for (int i start; i nums.size(); i) { path.push_back(nums[i]); dfs(nums, i 1); path.pop_back(); } }有重复元素的子集就要去重了。做法是先排序然后在循环里加一句判断如果i start且nums[i] nums[i-1]就跳过。这句话的含义是——同一层里相同的值只取第一个后面的重复值剪掉。注意判断条件是i start而不是i 0因为i 0会把不同层的相同值也误伤导致结果丢解。这一点我在面试里被问过当时答错了回去改了半天才想通。3.2 组合问题索引起点与剪枝组合和子集长得很像区别在于组合通常有长度限制比如从 n 个数里选 k 个。结束条件变成path.size() k。剪枝点在 for 循环的上界如果剩下的元素数量不足以凑满 k 个就可以直接 break。具体怎么算当前已经选了path.size()个还需要k - path.size()个。假如从下标 i 开始选那么 i 到 n-1 一共有n - i个元素可用。当n - i k - path.size()时说明怎么选都不够这一层后面都不用试了。整理一下就是循环条件写成i n - (k - path.size())。这个式子我建议你手动代入几个值验算一遍比死记要牢。组合总和这类题还要处理元素可以重复使用的变体区别是递归时传i而不是i 1。至于去重依旧是排序加同层跳过那一套。3.3 排列问题used数组与去重排列和组合最大的区别是元素有序所以不能用 start 限制范围否则会漏掉先选后面的再选前面的这种排列。解决办法是用一个 used 数组记录每个元素是否已在当前路径中循环每次都从 0 开始。void dfs(vectorint nums) { if (path.size() nums.size()) { res.push_back(path); return; } for (int i 0; i nums.size(); i) { if (used[i]) continue; if (i 0 nums[i] nums[i-1] !used[i-1]) continue; // 去重 used[i] true; path.push_back(nums[i]); dfs(nums); path.pop_back(); used[i] false; } }这里的去重判断要格外小心。nums[i] nums[i-1] !used[i-1]的意思是前一个相同的数在这一层还没被用过说明它们是同一层的重复分支跳过。如果used[i-1]为真说明前一个数在上层已经选过了当前这个是不同层的合法选择不能跳。这个!号写反结果会直接错我自己就写反过一次。3.4 切割与棋盘类问题切割类的代表是分割回文串、复原 IP 地址它们的选择不是某个元素而是从当前位置切一段子串出来。循环变量从 start 开始表示切割点切出来的子串要满足题目条件才能继续递归。结束条件是切割点到达字符串末尾。棋盘类的代表是 N 皇后和数独决策维度从一维变成二维但套路不变按行逐层放置每行遍历所有列作为选择列表判断当前位置是否合法合法就放、递归、再撤销。区别在于合法性判断更复杂需要额外的标记结构来加速这部分放到实操章节细讲。4. 剪枝把指数级暴力压下来的关键回溯不加剪枝复杂度基本是 2 的 n 次方、n 的阶乘这个量级。n20 的时候 2^20 大约一百万还能忍n30 就是十亿肯定超时。剪枝的意义就是在搜索树上提前砍枝让实际访问的节点数远远少于理论上界。我把剪枝分成三类可行性剪枝、最优性剪枝、去重剪枝。4.1 可行性剪枝与最优性剪枝可行性剪枝判断的是这条路还能不能走通。组合问题的剩余元素不足就是典型N 皇后的列冲突、对角线冲突也是。它的特点是判断依据来自当前状态 约束条件跟最终目标无关。最优性剪枝判断的是这条路即使走通也不会更优。它只出现在求解最值类问题里比如旅行商问题、分割等和子集。写的时候要先有一个当前最优解然后每层估计剩余部分的理论下界如果已花代价 下界 当前最优直接剪掉。这里的下界估计必须乐观估得偏小否则会误剪掉真正的最优解这是最优性剪枝的唯一准则。我的经验是先确认题目要的是所有方案还是最优方案前者只能用可行性剪枝后者才能上最优性剪枝。用错了方向要么白剪要么剪错。4.2 排序加跳过重复的写法去重剪枝的通用套路可以总结成三步第一步对原始数据排序让相同的元素聚在一起第二步在循环里判断当前元素是否与前一个相同第三步根据同一层还是不同层决定是跳过还是保留。不同题型的判断细节略有出入。子集和组合用i start的方式因为它们的可选范围由 start 界定。排列因为每层都从 0 开始必须借助 used 数组来判断层关系。写的时候脑子里要清楚排序是前提没有排序相同元素不挨着跳过逻辑就失效。还有一种写法是把结果放进set里自动去重。这种写法我强烈不推荐——它是在结果层去重搜索树里的重复分支还是照样跑复杂度没有任何改善。n 稍大一点就超时而且set存vector还要额外写比较逻辑费力不讨好。4.3 记忆化与回溯的边界有同学会问回溯能不能加记忆化答案是可以但要谨慎。记忆化搜索要求相同状态的结果可复用而回溯的状态往往包含路径信息如果路径不同但剩余选择相同理论上可以复用。这时候需要把状态比如剩余可选集合、当前约束用一个可哈希的 key 表示出来缓存子问题的结果。但注意如果题目要求的是列出所有方案而不是求方案数量记忆化就帮不上忙因为每个方案都是不同的缓存不了具体路径。只有求解有多少种方案或者最优值是多少时记忆化才有意义。这也是为什么纯回溯题和动态规划题有时看着像但其实目标不同——一个要枚举一个要计数。提示当你在回溯题里想加记忆化时先问自己一句这道题是要输出所有方案还是只要一个数只要一个数才值得考虑缓存。5. 实操过程N皇后与数独的完整实现前面讲的都是框架这一章拿两个经典题走一遍完整流程把参数怎么定、判重怎么做、性能怎么测都说清楚。我建议你自己先不看代码写一遍再对照着找差异效果比直接抄要好得多。5.1 N皇后的对角线判重技巧N 皇后的规则是每行放一个皇后且任意两个皇后不能同列、同主对角线、同副对角线。行号天然不冲突所以决策按行推进每层的选择列表是该行的所有列。判重的朴素做法是每次放置前遍历已放的皇后逐个检查冲突复杂度 O(n)。但有个更快的技巧用三个布尔数组分别记录列、主对角线、副对角线是否被占用。主对角线的特征是row - col为定值范围是-(n-1)到n-1加个偏移n-1映射到非负下标副对角线的特征是row col为定值范围 0 到2n-2。这样每次判断和修改都是 O(1)。class Solution { vectorvectorstring res; vectorstring board; vectorbool col, diag1, diag2; int n; public: vectorvectorstring solveNQueens(int N) { n N; board.assign(n, string(n, .)); col.assign(n, false); diag1.assign(2 * n - 1, false); diag2.assign(2 * n - 1, false); dfs(0); return res; } void dfs(int row) { if (row n) { res.push_back(board); return; } for (int c 0; c n; c) { int d1 row - c n - 1; int d2 row c; if (col[c] || diag1[d1] || diag2[d2]) continue; board[row][c] Q; col[c] diag1[d1] diag2[d2] true; dfs(row 1); board[row][c] .; col[c] diag1[d1] diag2[d2] false; } } };实测 n8 时求解时间在毫秒级n10 也能秒出n12 就明显变慢这是搜索树规模决定的跟判重快慢关系不大。判重从 O(n) 降到 O(1) 主要影响的是比较大的 n。5.2 数独的位运算加速数独比 N 皇后更复杂因为约束有三个方向行、列、九宫格。每个格子要填 1 到 9 中的一个数且所在行、列、宫都不能重复。朴素写法是用三个二维布尔数组rowUsed[9][9]、colUsed[9][9]、boxUsed[9][9]记录每个数字是否出现。但用位运算可以省掉一层数组每个行、列、宫只用一个整数表示第 d 位为 1 表示数字 d1 已被占用。int rowMask[9], colMask[9], boxMask[9]; inline int boxId(int r, int c) { return (r / 3) * 3 c / 3; // 九宫格编号 0..8 } bool dfs(vectorvectorchar board, int pos) { if (pos 81) return true; int r pos / 9, c pos % 9; if (board[r][c] ! .) return dfs(board, pos 1); int b boxId(r, c); int used rowMask[r] | colMask[c] | boxMask[b]; for (int d 0; d 9; d) { if (used d 1) continue; board[r][c] char(1 d); rowMask[r] | 1 d; colMask[c] | 1 d; boxMask[b] | 1 d; if (dfs(board, pos 1)) return true; board[r][c] .; rowMask[r] ~(1 d); colMask[c] ~(1 d); boxMask[b] ~(1 d); } return false; }用整数位代替布尔数组判断可用数字时一句used row | col | box就够了遍历九个数字时用位移检查。这个写法在一道难度中等的数独上实测比布尔数组版本快三成左右代码还短。宫格编号公式(r/3)*3 c/3是重点记住这个就能把二维坐标正确映射到九个格子。5.3 调试与性能测试记录我调试回溯代码有个固定习惯先构造一个最小规模用例手动推演输出再跟程序结果比对。比如全排列用[1,2]子集用[1,2,3]N 皇后用 n4。小规模时输出的方案数我能心算出来对不上就说明逻辑错了这时候再去看代码。性能测试我用chrono计时把 dfs 调用包起来auto t0 chrono::high_resolution_clock::now(); auto ans solveNQueens(10); auto t1 chrono::high_resolution_clock::now(); cout chrono::durationdouble, milli(t1 - t0).count() ms\n;这样能直观看到加剪枝前后、换判重方式前后的差异。注意别用clock()它在多线程或者某些平台上不准chrono的high_resolution_clock更靠谱。测的时候记得把输出关掉或者重定向I/O 会掩盖真实计算时间。6. 常见问题与排查技巧实录回溯的 bug 有个特点现象千奇百怪但根因就那么几个。我把自己和身边同学踩过的坑整理成一份速查表遇到问题先对号入座基本能定位到方向。6.1 高频踩坑速查表现象可能原因排查方向结果里元素重复出现、越来越多push_back 后没有对应 pop_back检查每处做选择后是否都撤销结果数量比预期多有重复方案去重逻辑缺失或判断条件写错确认已排序检查同层跳过条件结果数量比预期少、丢解剪枝条件过严临时去掉剪枝对比结果某些方案元素顺序不对排列用了 start 限制排列应使用 used 数组而非起点结果集里所有方案都是同一个收集的是引用而非副本result 收集路径时要拷贝大数据超时未剪枝或去重放在结果层上可行性剪枝去重前移到搜索层这张表我贴在显示器边上用了小半年后来形成条件反射看现象就能猜到问题。特别提醒两条路径的收集一定要拷贝res.push_back(path)是拷贝res.push_back(move(path))就会把 path 搬空下一层撤销时直接崩去重一定要在搜索过程中做不要事后去重。6.2 传参传引用带来的隐藏bug这是最难查的一类问题因为代码逻辑看起来完全正确但结果就是不对。根源在于 C 的引用语义。如果你把path用引用传进递归同时又在函数里对path做了修改而没有撤销那么回到上层时 path 已经被污染了。举个例子某次我图省事在切分子串的题里把子串按值构建后 push 进 path递归回来忘了 pop。小数据看不出来因为恰好每个分支都多带了一个元素结果数量没错但内容全错了。这种 bug 用打印调试很费劲我的办法是在每层 dfs 入口打印 path 的当前内容对比决策树的预期路径一眼就能看出哪层多了东西。另一个相关坑是成员变量和局部变量混用。如果你在类里定义了path成员又在一个函数里定义同名局部变量很容易改错对象。我现在的习惯是所有共享状态统一用类成员函数里不再定义同名局部变量。6.3 复杂度估算与超时排查回溯题的复杂度不能只看循环层数。子集是 O(2^n)因为每个元素选或不选两种状态排列是 O(n!)每个位置都要从剩余元素里挑一个组合是 O(C(n,k) * k)每个方案拷贝耗时 kN 皇后实际远小于 O(n!)因为有大量剪枝。排查超时按这个顺序走第一确认去重和剪枝是否都加上了第二看路径收集有没有不必要的拷贝能用移动语义的地方用上第三评估一下题目规模如果 n 到了 30 而你写的是 2^n那不是代码问题是算法需要换比如改成动态规划或者 meet-in-the-middle第四检查有没有把结果去重放在最后统一处理能前移就前移。我个人的体会是大部分回溯超时其实不是算法选错了而是剪枝漏了或者写错了。真到需要换算法的规模题目通常会给出更明显的提示比如数据范围特别大、或者要求的是计数而不是枚举。先把手上的剪枝和去重做扎实绝大多数中等难度题都能稳稳过掉。写到这里回溯这块基本就捋顺了。我的建议是找十道题动手写一遍覆盖子集、组合、排列、切割、N 皇后这几类写完对照模板检查三要素和撤销逻辑。这一步做完再去碰记忆化搜索和图论 DFS会感觉顺理成章。