第8类题型回溯为什么回溯题你明明背过模板一到面试还是容易把搜索树写乱很多同学第一次学回溯会觉得它就是一套固定模板path.add()、递归、path.remove()。但真正到了面试现场回溯往往比二分、链表更容易让人慌。原因不是代码长而是你没有先把“这道题对应的是一棵什么样的搜索树”想清楚。回溯题最常见的翻车方式通常有这几种你会背模板但说不清路径、选择列表、结束条件分别是什么。你知道要递归却讲不清为什么这里要start那里又要used[]。你把“撤销选择”当成模板动作在机械执行没理解它为什么是恢复现场的必要步骤。如果你现在处在“看题知道大概是回溯但一写就容易乱”的阶段这一类题特别值得单独练透。读完这篇你至少要把 3 件事练熟先把题目翻译成搜索树、先判断它是组合/排列/子集哪一类、能在面试里解释为什么这一步必须撤销选择。文章目录第8类题型回溯为什么回溯题你明明背过模板一到面试还是容易把搜索树写乱1. 核心知识点动画辅助理解回溯真正回去的是什么2. 这类题在面试里考什么3. 高频题清单4. 这类题最容易犯的 3 个错误5. 代表题精讲 1题目思路Java 代码复杂度边界提醒如果这是面试现场你可以这样说6. 代表题精讲 2题目思路Java 代码复杂度边界提醒如果这是面试现场你可以这样说7. 其余题模板与关键片段[78. 子集](https://leetcode.cn/problems/subsets/)[17. 电话号码的字母组合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/)8. 回溯题先判断什么9. 错题本记录方式10. 面试前 3 分钟速记11. 最后总结回溯真正难的不是模板而是搜索树视角1. 核心知识点回溯本质上是在一棵隐式搜索树上做 DFS。题目表面看起来不同但你真正要先讲清楚的永远是这 3 件事路径当前已经选了什么。选择列表下一步还能选什么。结束条件什么时候把当前路径收进答案。通用模板voidbacktrack(...){if(满足结束条件){result.add(newArrayList(path));return;}for(inti起点;i选择列表大小;i){path.add(当前选择);backtrack(...);path.remove(path.size()-1);}}很多人学回溯容易乱是因为把上面这段代码当成“公式”却没理解每个位置在控制什么path.add(...)是把当前节点的选择压进路径。递归是往下一层走继续扩展这条路径。path.remove(...)不是可选动作而是回到上一层前恢复现场。动画辅助理解回溯真正回去的是什么你可以先打开这页分步动画回溯做选择、递归、撤销选择分步动画如果你准备发在不支持 iframe 的平台也可以直接放慢速 GIF让读者先建立“搜索树走下去又退回来”的直觉这个动画最值得盯住的是 4 步先看当前路径path里已经选了什么。再从选择列表里拿一个候选做出当前选择。然后递归进入下一层继续扩展这条路径。最后回到上一层撤销刚才的选择保证同层其他分支不被污染。拿nums [1, 2, 3]的子集题举例假设当前从空路径开始步骤当前路径当前动作含义1[]收集答案空集本身也是一个合法子集2[] - [1]选1进入“包含 1”的分支3[1] - [1,2]再选2继续向下扩展当前路径4[1,2] - [1]撤销2回到上一层准备尝试3这张表最重要的不是具体答案而是你要看清楚回溯并不是“瞎试”而是在一条路径上向下探索走不下去或者收集完结果后再退回来尝试下一个选择。2. 这类题在面试里考什么回溯题真正考的不是你能不能背出模板而是你能不能把题目抽象成搜索树并且稳定地控制状态。面试官通常会看你能不能把题目翻译成路径、选择列表、结束条件。你能不能区分组合、排列、子集这几种搜索树。你是否理解start和used[]分别在控制什么。你会不会在递归回来后恢复现场避免状态污染。真正的区分度在于你不只是把代码写出来还能解释为什么当前这条分支该继续、为什么另一条分支不能复用刚才的状态。3. 高频题清单题目来源难度高频属性77. 组合面试经典 150Medium基础高频78. 子集LeetCode 热题 100Medium高频46. 全排列LeetCode 热题 100Medium高频 Medium17. 电话号码的字母组合面试经典 150Medium常见4. 这类题最容易犯的 3 个错误只会套模板讲不出路径、选择列表和结束条件。递归回来后忘了撤销选择导致同层分支互相污染。组合、排列、子集混着写不知道什么时候该用start什么时候必须用used[]。5. 代表题精讲 1题目77. 组合思路这题要从1..n中选出k个数。每次选完一个数后后续只能从更大的数继续选因此它是一道非常标准的组合问题。你可以把它想成这样一棵树第一层决定第 1 个数选谁。第二层决定第 2 个数选谁。每往下一层候选范围都要从当前数后面开始避免重复。这里最关键的不是代码而是这个start参数。它的作用不是“模板规定要传”而是告诉下一层前面已经选过的数不要再回头选了。Java 代码importjava.util.ArrayList;importjava.util.List;classSolution{privatefinalListListIntegerresultnewArrayList();privatefinalListIntegerpathnewArrayList();publicListListIntegercombine(intn,intk){backtrack(1,n,k);returnresult;}privatevoidbacktrack(intstart,intn,intk){if(path.size()k){result.add(newArrayList(path));return;}for(intistart;in;i){path.add(i);backtrack(i1,n,k);path.remove(path.size()-1);}}}复杂度时间复杂度与答案规模相关空间复杂度O(k)不计答案空间边界提醒这题最容易错的不是“会不会回溯”而是“会不会重复选已经走过的元素”。比如你已经在路径里选了2下一层如果还允许从1再开始选就会把[2,1]这种本质和[1,2]重复的答案也搜出来。组合题里顺序不重要所以你必须用start把搜索范围限制在当前元素之后。如果这是面试现场你可以这样说这题我会把它抽象成组合搜索树。路径里保存当前已经选的数字结束条件是路径长度等于k。因为组合不关心顺序所以递归到下一层时我只允许从当前数字后面继续选也就是用start控制搜索范围避免把同一组数字按不同顺序重复收集。6. 代表题精讲 2题目46. 全排列思路排列和组合最大的区别在于顺序不同答案就不同。这意味着什么组合里选过的前面元素后面不能回头再选。排列里每一层都要重新从所有元素里挑但只能选“当前路径中还没使用过”的元素。因此这题必须用used[]标记某个元素是否已经在当前路径里用过。Java 代码importjava.util.ArrayList;importjava.util.List;classSolution{privatefinalListListIntegerresultnewArrayList();privatefinalListIntegerpathnewArrayList();privateboolean[]used;publicListListIntegerpermute(int[]nums){usednewboolean[nums.length];backtrack(nums);returnresult;}privatevoidbacktrack(int[]nums){if(path.size()nums.length){result.add(newArrayList(path));return;}for(inti0;inums.length;i){if(used[i]){continue;}used[i]true;path.add(nums[i]);backtrack(nums);path.remove(path.size()-1);used[i]false;}}}复杂度时间复杂度与答案规模相关空间复杂度O(n)不计答案空间边界提醒这题最容易错的点有两个忘了used[]导致同一个元素在一条路径里被重复选中。只做了path.remove(...)却忘了把used[i]改回false导致别的分支误以为这个元素已经被占用了。所以回溯题里的“撤销选择”常常不是一行代码而是一组状态恢复动作。路径恢复了标记数组、和、棋盘、字符串长度这些状态也都要一起恢复。如果这是面试现场你可以这样说这题和组合不同因为排列里顺序有意义所以每一层都可以从所有元素里继续选。但为了避免同一个元素在一条路径里重复出现我会用used[]记录当前路径已经占用的元素。递归回来后不仅要把路径最后一个元素删掉还要把对应的used[i]恢复成false这样同层其他分支才能正常尝试它。7. 其余题模板与关键片段78. 子集子集题和组合题很像但最关键的区别是它不是只在叶子节点收集答案而是每到一个节点都可以先收集当前路径。result.add(newArrayList(path));for(intistart;inums.length;i){path.add(nums[i]);backtrack(i1,nums);path.remove(path.size()-1);}为什么要先收集因为子集允许长度为0、1、2...n的所有路径所以当前节点本身就已经代表一个合法答案了。17. 电话号码的字母组合这题的路径是当前拼出来的字符串选择列表来自当前数字对应的字符映射。和组合题不同它不是在数组里选元素而是在每一层根据一位数字去扩展字符。边界上最容易漏的是空字符串输入digits为空时应该直接返回空结果而不是返回包含空串的列表。8. 回溯题先判断什么真正动手写之前你可以先问自己 4 个问题这题的路径里到底保存的是什么。这一层还能从哪些候选里继续选。我是在什么时候收集答案是叶子节点还是每个节点。当前这题需要start控制范围还是需要used[]控制是否已使用。这 4 个问题一旦先问清楚回溯题大部分“写着写着就乱”的情况都会明显减少。9. 错题本记录方式回溯题建议重点记录这题的路径是什么。这题的选择列表是什么。结束条件到底是什么。收集答案的时机在叶子节点还是中间节点。这题为什么要start或者为什么必须要used[]。10. 面试前 3 分钟速记回溯先说路径、选择列表、结束条件。组合从start往后选避免重复。排列每层都能从所有元素里选但要used[]。子集通常每个节点都能收集答案。撤销选择不是装样子而是在恢复现场。11. 最后总结回溯真正难的不是模板而是搜索树视角如果你只能记住一句话那就是回溯题最怕的不是不会写模板而是你根本没先想清楚当前这道题的搜索树长什么样。面试时你只要按这个顺序去讲思路就会稳很多先说明路径里保存什么。再说明这一层还能从哪些候选里选。接着说答案是在什么时候收集。最后补一句当前这题为什么该用start或used[]。这样你就不只是会背add - recurse - remove而是真的掌握了回溯题的公共骨架。上期速递【Java实习面试算法冲刺】二分感谢阅读记得点赞、关注、收藏欢迎各位评论区交流