回溯算法在力扣Hot 100里属于那种“看起来题型不多真上手却容易卡壳”的模块。我刷了三轮Hot 100每次都在回溯这块栽过跟头要么是递归出口想不清楚要么是结果集全是空列表要么是去重逻辑写错导致超时。今天借着“力扣hot100—系列8-回溯算法”这个专题把排列、组合、子集、棋盘、字符串这几类高频题串起来做一次彻底复盘把模板、剪枝、去重、复杂度这些核心东西一次说透。无论你是在按力扣刷题顺序推进的新手还是准备面试前想快速过一遍回溯的老手这篇文章都值得花一小时认真读完。1. 回溯到底在解什么题核心思路与题型分布1.1 Hot 100里回溯题的真实画像先看Hot 100里和回溯强相关的题目全排列、全排列II、组合总和、组合总和II、子集、子集II、括号生成、单词搜索、分割回文串、N皇后偶尔还有复原IP地址这类变体。这些题表面上天差地别底层全部是同一套东西在一个多阶段决策问题里不断做选择发现走不通就回头换一条路。我一开始刷的时候犯过一个典型错误把每道题当作独立题型去背解法。全排列背一个写法子集背一个写法组合总和背一个写法结果题目稍微变一下就不会了。后来才意识到回溯从来不是“背模板”而是“理解决策树”。全排列是每一层选一个没选过的数组合是每一层从当前下标往后选子集是每一层决定“要不要当前数”括号生成是每一层决定“放左括号还是右括号”。一旦理解到这一层Hot 100里那批回溯题就变成同一道题换了几套马甲。另一个容易忽略的事实是回溯题在面试中的出现频率极高因为面试官能通过一道回溯题快速考察你的递归功底、状态管理能力、复杂度分析水平和优化意识。一个候选人能不能把回溯写出“无重复、无遗漏、不超时”基本能看出刷题有没有真正形成体系。这也是为什么Hot 100把回溯单列成一个系列值得反复刷、反复总结。1.2 回溯和普通DFS的区别找路径VS搜状态很多教程会把回溯和深度优先搜索混在一起讲但它们有两个关键区别。第一回溯关注的是“路径”也就是从根到当前节点的完整选择序列。DFS往往只关心“能否到达某个节点”或“遍历所有节点”而回溯关心的是“记录下了哪条路”。所以回溯几乎必然有一个 path 或 track 变量每次递归进入下一层时把当前选择追加进去。第二回溯必须做“状态回滚”。因为一整棵决策树共用同一个 path当递归从子节点返回父节点时如果不把路径恢复原样下一轮循环里 path 就越攒越长结果就是各种匪夷所思的输出。这个细节我见过太多人踩坑明明递归出口写对了结果收集到的 path 全是一样的或者集齐所有排列后发现每个排列后面都多了一截别的路径的尾巴。DFS 的经典应用比如岛屿数量、二叉树遍历往往不需要回滚因为每个节点只需访问一次。而回溯要的是“换一种选择重新走一遍”这就决定了同一份数据会被反复改写。这个本质差异理解透了后面看模板就顺理成章了。2. 先吃透模板回溯代码的三段式结构与状态回滚2.1 一个覆盖80%场景的通用模板回溯代码的骨架其实极其稳定Hot 100里绝大多数回溯题都能套进下面这个模板。我用Java写因为力扣上Java代码的可读性和调试体验都比较友好。void backtrack(参数列表) { if (满足结束条件) { 收集结果; return; } for (选择 : 当前层的可选集合) { 做选择; backtrack(新的参数列表); 撤销选择; } }是不是觉得太简单了但真正要写出能AC的版本难点全在“参数列表”和“剪枝条件”上。以全排列为例完整代码长这样class Solution { ListListInteger res new ArrayList(); ListInteger path new ArrayList(); public ListListInteger permute(int[] nums) { boolean[] used new boolean[nums.length]; backtrack(nums, used); return res; } private void backtrack(int[] nums, boolean[] used) { if (path.size() nums.length) { res.add(new ArrayList(path)); return; } for (int i 0; i nums.length; i) { if (used[i]) { continue; } used[i] true; path.add(nums[i]); backtrack(nums, used); path.remove(path.size() - 1); used[i] false; } } }这个代码有两处最容易被忽略一是收集结果时写的是new ArrayList(path)不是res.add(path)二是撤销选择时必须把used[i]和path同步恢复。这两个点就是回溯正确性的命门我会在下一节展开讲为什么。组合总和、子集、分割回文串本质上只是把“循环起点怎么定”和“递归参数怎么传”做调整。比如组合总和用startIndex控制每层从哪个位置开始选子集每次进入递归就把当前 path 收集进结果括号生成用左右括号的剩余数量控制选择集合。模板本身不变变的是套模板的思路。2.2 三个高频翻车点引用拷贝、回滚顺序、参数传递先说引用拷贝。我见过太多人写出过这样的代码res.add(path); // 错误写法收集结果时如果直接把 path 塞进结果集存进去的只是一个引用。回溯继续往下走时path 的元素被不断增删最终结果集里所有列表都指向同一份当前状态。等到回溯结束path 回到空列表结果集里就全是空列表。正确做法永远是res.add(new ArrayList(path))或者该语言对应的拷贝操作。再说回滚顺序。做选择和撤销选择必须严格对称。如果你先path.add再used[i] true撤销时也应该先path.remove再used[i] false。当然顺序反过来也能跑通但最好固定成“添加和标记同步、删除和取消标记同步”否则在复杂题里很容易漏掉一边。我习惯把“做选择”和“撤销选择”写成上下紧挨着的两行一眼就能检查对称性。最后是参数传递。Java里基本类型按值传递数组和集合按引用传递。如果你在递归中试图通过“修改传入的List参数”来控制状态大概率会得到一份被全局污染的路径。一个干净的做法是可变状态全部用成员变量或者显式的集合来维护递归参数只传“下标、剩余次数、目标值”这类不可变信息。这样调试时心智负担会小很多。3. 剪枝是灵魂Hot 100里最常用的两类剪枝3.1 重复元素去重排序同一层跳过如果题目给的输入里有重复元素比如全排列II、组合总和II、子集II不做剪枝就会产生大量重复结果。最常见的做法是先把数组排序然后在循环里加一个判断if (i startIndex nums[i] nums[i - 1] !used[i - 1]) { continue; }但很多教程只给结论不讲为什么导致换个场景就写错。这里的关键在于区分“同一层重复”和“不同层重复”。拿全排列II举例数组[1, 1, 2]。两个1是完全相同的元素如果在同一层循环里第一个1选过了第二个1再选就会产生重复排列。但如果是第一个1走完一整条路径后在下一层递归里出现了第二个1这时是可以选的因为两条路径在数组下标上确实不同。所以去重条件的核心是“只有当 nums[i] 和前一个数相同且前一个数没有在当前的路径状态中被使用时才跳过本次选择”。有两点特别容易出错。第一排序是这类去重的前提不排序就无法判断“前一个相同的数是否已经处理过”。第二!used[i - 1]和used[i - 1]这两种写法都能去重但语义不同一个保留的是左侧兄弟子树一个保留的是左侧父节点路径。我强烈建议初学者统一采用!used[i - 1]这样更容易理解成“上一个相同元素如果已经回溯完毕说明当前分支和它重复跳过”。为了让你看得更清楚我用表格整理一下四道排列组合类题目的去重差异题目是否排序去重条件说明组合总和否不需要元素本身不重复且可无限复用组合总和II是i startIndex nums[i] nums[i - 1]每个元素只能用一次同层跳过重复全排列否不需要元素本身不重复全排列II是i 0 nums[i] nums[i - 1] !used[i - 1]排列中同层跳过重复3.2 约束剪枝与提前终止除了去重回溯还有一类剪枝是基于题目约束的提前终止。最典型的例子是括号生成如果当前右括号数量已经大于左括号数量说明已经出现了非法前缀没必要继续递归。组合总和中如果当前 target 已经减到小于0也没必要继续选数。N皇后里如果当前位置和之前的皇后同列或同对角线直接跳过。我第一次写括号生成时没有加剪枝结果生成了大量无效字符串再过滤代码又长又慢。后来改成在每次递归前判断if (right left) { return; }瞬间代码量减少一半逻辑也更清晰。这里的本质是回溯本身就是在遍历决策树而剪枝是在进入某个分支之前就判断“这个分支不可能产生合法答案”从而砍掉整棵子树。有没有剪枝往往决定了一道题是AC还是TLE。剪枝位置的选取也有讲究。有些人喜欢在递归函数一进来就判断有些人喜欢在 for 循环里判断。我的经验是像括号生成这种和当前路径状态强相关的剪枝放在递归入口处判断代码更集中像组合总和这种和候选元素相关的剪枝放在循环里判断能提前避免一次递归调用。两种方式没有绝对的对错但一定要写清楚注释否则一个月后回看代码很容易忘记当时为什么这么剪。4. Hot 100回溯题逐题拆解从模板到场景4.1 组合总和与组合总和IIstartIndex与去重一网打尽组合总和39题是所有回溯题里最适合入门的一道因为它没有重复元素也没有“每个元素只能用一次”的限制只需要思考“怎么避免选中同样组合的不同顺序”。答案是 startIndex。每一层循环从 startIndex 开始递归时把i而不是i1传给下一层这样同一个元素可以重复选取同时因为每次都是从当前下标往后选就不会出现[2, 3, 2]这种乱序重复。核心代码如下private void backtrack(int[] candidates, int target, int startIndex) { if (target 0) { return; } if (target 0) { res.add(new ArrayList(path)); return; } for (int i startIndex; i candidates.length; i) { path.add(candidates[i]); backtrack(candidates, target - candidates[i], i); path.remove(path.size() - 1); } }组合总和II40题则是在此基础上加了两个限制每个数字在每个组合中只能使用一次且数组里有重复元素。于是递归参数从i变成i 1同时需要排序后去重。这里有个细节排序必须放在入口处不能放在递归里——如果你每次递归都排序时间和逻辑都会乱掉。另外我建议你手写一遍“输入[10,1,2,7,6,1,5], target8”的完整决策树特别是去重那一步是怎么跳过第二个1的。手写一遍之后你对“同层去重”的理解会牢靠很多。我当初就是靠着这个用例彻底搞懂了为什么去重条件是i startIndex而不是i 0。4.2 子集与子集II其实是在遍历决策树的每个节点全排列是收集“叶子节点”组合是收集“满足条件的叶子节点”而子集是收集“所有节点”。这句话是我在刷子集题时想明白的。子集问题的递归出口不用专门等到底因为每个路径状态都是一个合法子集所以进入递归函数的第一步就把 path 加入结果集。private void backtrack(int[] nums, int startIndex) { res.add(new ArrayList(path)); for (int i startIndex; i nums.length; i) { path.add(nums[i]); backtrack(nums, i 1); path.remove(path.size() - 1); } }注意这里backtrack的第一次调用发生在循环之前所以空集[]会自然被收集进去。很多人问过“为什么子集的结果里总有一个空集”答案就在这根节点本身就是一个合法状态。子集II90题和组合总和II的去重思路一模一样同样是排序后同层跳过。我一直觉得子集II是检验去重理解是否到位的最好题目因为它的结果集是完整的决策树所有节点一旦去重条件写错你能肉眼看到漏掉或重复的结果排错比组合题直观很多。4.3 全排列与全排列IIused数组的正确打开方式全排列类题目的核心是 used 数组。组合靠 startIndex 避免回头选排列不能这么干因为排列允许[1, 2, 3]和[3, 2, 1]同时出现。那怎么保证同一个元素不被重复使用只能额外维护一个 boolean 数组记录当前路径上哪些下标已经被选中。全排列还有一个容易被忽略的小优化如果数组长度已知可以在下标到达末尾时直接收集结果不必每次都判断path.size()。这两种写法都能AC但我觉得用path.size() nums.length语义更清晰适合初学者。全排列II的难点还是在去重。我见过不少人对nums[i] nums[i - 1] !used[i - 1]完全理解但一到手写就写成used[i - 1]导致结果直接清空或者重复。这里我再强调一次!used[i - 1]的含义是“前一个相同元素已经回溯结束不在当前路径上”此时选择当前元素会产生和之前某个兄弟分支完全相同的排列所以跳过而used[i - 1]的含义是“前一个相同元素在当前路径上”这时跳过的是“当前路径里连续两个相同元素”的场景逻辑完全不是一回事。用两个1的场景复盘一下[1a, 1b, 2]如果第一层选了1a第二层选了1b这是合法路径。此时used[0] trueused[1] true走到第三层时i 2没有重复问题。而当第一层选了1b时下一层i 0遇到1aused[0] falsenums[0] nums[1]于是跳过1a。这就保证了以1b开头的分支不会重复生成以1a开头的分支的结果。4.4 经典场景题括号生成、单词搜索与N皇后括号生成22题是回溯里思想最简单但代码最需要克制的一道。它不涉及数组下标也没有去重只需要维护 left 和 right 两个计数。每层递归有两种选择放左括号或放右括号。唯一的约束是剩余右括号数不能少于剩余左括号数否则前缀非法。我当时写的版本是这样private void backtrack(int left, int right, StringBuilder sb) { if (left 0 right 0) { res.add(sb.toString()); return; } if (left 0) { sb.append((); backtrack(left - 1, right, sb); sb.deleteCharAt(sb.length() - 1); } if (right left) { sb.append()); backtrack(left, right - 1, sb); sb.deleteCharAt(sb.length() - 1); } }注意这里用的是 StringBuilder撤销操作是deleteCharAt。如果你用 String 直接拼接每次递归会生成新对象不用回滚也能跑但会生成很多中间字符串内存和性能都不理想。这个细节在面试时主动提一下是个不错的加分点。单词搜索79题是回溯在矩阵上的经典应用。它是在二维网格里找一条路径匹配目标字符串。核心思路是遍历每个格子作为起点从起点做回溯上下左右四个方向搜索。搜索时需要标记当前格子已访问防止路径绕回原点。我的标记方法是把当前格子临时改成#递归返回后再改回来。这样避免额外创建 visited 数组。不过要注意如果矩阵里本来就包含#字符这种方法会出 bug所以更稳妥的方案还是创建一个 boolean 数组。N皇后51题是回溯里偏难的一道但Hot 100既然选了它就说明它考察的是核心能力如何高效判断“当前位置是否合法”。很多解法会用三数组或两数组记录列、两条对角线的占用情况。核心公式是主对角线的row - col是常数副对角线的row col是常数。用这个特性判断冲突就是O(1)的。第一次写N皇后时我差点被“同对角线判断”搞崩后来把公式写在注释里才算彻底顺了。这道题如果你觉得难可以先跳过但刷完前面几道基础回溯题后一定要回来补上。5. 实战中的常见问题与避坑备忘录5.1 结果集被清空、输出重复、性能超时的排查我在刷回溯题过程中把踩过的坑整理成了一个速查表。遇到问题先对着这个表排查基本能快速定位80%的bug。现象可能原因解决办法结果集全是空列表收集结果时没有拷贝 pathres.add(new ArrayList(path))结果集元素数量对但内容重复缺少同层去重或去重条件写错排序后检查i startIndex或!used[i - 1]结果集缺失部分组合startIndex 传错导致跳过了一些元素组合题递归传i 1组合总和传i递归栈溢出递归出口缺失或终止条件错误检查是否在所有分支上都能达到终止条件时间复杂度过高导致超时缺少剪枝或剪枝条件位置不对把约束剪枝放在递归入口或循环内提前判断每条我都亲自踩过。以“结果集全是空列表”为例我第一次写全排列时以为res.add(path)没问题结果输出[[], [], [], [], [], []]愣是看了半天才反应过来是引用问题。从那时起我给自己定了规矩凡是往结果集里 add 的东西一律拷贝不拷贝不提交。5.2 回溯debug的土办法回溯代码不好调试因为状态在不断变化你很难从中间打断观察。我试过IDE断点、打印日志最后发现最有效的土办法是在递归入口增加一个depth参数或变量然后打印带缩进的状态信息。private void backtrack(int[] nums, int depth, boolean[] used) { System.out.println( .repeat(depth) path path); ... }这样你就能直观看到每层递归进入时的路径状态、退出后的回滚状态。对于小规模输入比如[1, 2, 3]打印出来就是一整棵决策树。虽然这个版本打印过多会导致超时但本地调试完全够用。建议额外加一个“只打印前20行”的开关避免输出爆炸。另一个技巧是主动构造最小规模输入来模拟。比如写全排列先跑[1]再跑[1, 2]再跑[1, 2, 3]。如果[1]的结果都不对不要直接去查大样例先回头看模板和递归出口。小规模输入能让你手动模拟每一步的状态变化比盯着日志猜半天有效得多。5.3 推荐的刷题顺序与时间规划如果按力扣刷题顺序来推进回溯我建议不要完全按照Hot 100的原顺序刷而是按由易到难的递进关系。我的推荐顺序是子集78最简单的回溯先理解决策树和路径收集组合总和39理解 startIndex 的意义全排列46理解 used 数组和状态回滚括号生成22理解约束剪枝子集II90理解同层去重组合总和II40去重startIndex 的综合全排列II47去重used 数组的综合分割回文串131回溯字符串处理单词搜索79回溯矩阵遍历N皇后51高级约束剪枝每道题至少写三遍。第一遍看题解抄代码理解每一行第二遍关掉题解从零写写不出来就回顾模板第三遍限时25分钟独立完成模拟面试状态。我一般是每天两题一周刷完这个小专题。不要小看“三遍法”很多题你第一遍觉得懂了第二遍照样卡住第三遍才能形成条件反射。关于要不要背模板我的观点是模板要背但更关键的是理解模板为什么这么写。真正到了面试现场面试官不会只满足于你默写出代码他会追问“这里是干什么的”“为什么要拷贝”“这里剪枝去掉会怎样”。回答不上来代码写得再快也白搭。6. 回溯题目复杂度分析与面试表达技巧6.1 怎么估算回溯题的复杂度回溯题的复杂度通常都不好看因为决策树的规模往往是指数级甚至阶乘级的。全排列的时间复杂度是 O(n!)因为第一层有 n 个选择第二层有 n-1 个选择以此类推。组合类问题最坏是 O(2^n)因为每个元素都有选和不选两种可能。子集的复杂度也是 O(2^n)因为2的n次方个节点。空间复杂度主要看递归深度。全排列的递归深度是 n子集也是 nN皇后也是 n所以空间复杂度一般是 O(n)。但要注意这个 O(n) 没有把结果集本身算进去。如果把返回值占用的空间也算上结果集可能大到 O(n! * n)但面试时通常只讨论“不考虑输出结果”的空间复杂度你可以在表达时主动说明“这里不考虑存储结果集所需的空间”显得更专业。剪枝会影响实际的运行时间但不会改变最坏情况复杂度。组合总和II加了去重理论上最坏仍是 O(2^n)但实际运行时间会快很多。面试时可以先给出最坏复杂度然后补充说“如果考虑剪枝平均情况会好很多”。我当时在面试字节和阿里时都遇到过追问回溯复杂度这么回答下来基本都能过关。6.2 面试时怎么把回溯题讲出层次感讲回溯题的时候不要一上来就写代码。我习惯按四步走第一确认题意和输入规模判断该用回溯第二画一棵小规模的决策树让面试官直观看到搜索空间第三说清楚每层选择的含义和递归出口第四指出哪些地方可以剪枝并直接实现。这个过程能把一场手写代码变成“有思路、有推理、有优化”的技术讨论面试评价会高不少。画决策树尤其重要。比如组合总和输入[2, 3, 5], target8你能在纸上画出根节点、第一层选2/3/5的三个分支、以及第二层的剪枝路径面试官基本就会点头了。我建议刷题时每道题都画一次决策树哪怕画得很潦草。画得多了你会发现回溯题的套路确实就是那么几个变体。另外一个小技巧在讲代码前先把“递归出口、循环选择、撤销选择”这三件事讲清楚然后边说边写。很多候选人写着写着把path.remove忘掉或者把used[i] false漏掉就是因为没有提前在脑子里过一遍“三段式”。先把模板说出来再填细节出错的概率会大幅下降。我个人刷完这一系列回溯题后最大的体会是回溯算法真正难的地方从来不是代码本身而是“能否在递归的每一层都想清楚当前状态”。一旦你把决策树、路径记录、状态回滚、剪枝这四件事融为一体Hot 100里的回溯题就真的只是同一道题换了几套马甲。如果时间有限我建议你把子集、组合总和、全排列、括号生成这四道题刷到“闭着眼都能写”的程度再去碰N皇后和单词搜索会发现一切都顺理成章。最后再分享一个我自己用着很舒服的练习方法每天晚上睡觉前在脑子里默写一遍回溯模板连写三天之后再遇到任何回溯题你的第一反应就不再是慌张而是拆解成“选什么、出口在哪、怎么剪枝”三个问题思路会清晰非常非常多。