【Java实习面试算法冲刺】回溯

第8类题型：回溯

为什么回溯题你明明背过模板，一到面试还是容易把搜索树写乱

很多同学第一次学回溯，会觉得它就是一套固定模板：path.add()、递归、path.remove()。但真正到了面试现场，回溯往往比二分、链表更容易让人慌。原因不是代码长，而是你没有先把“这道题对应的是一棵什么样的搜索树”想清楚。

回溯题最常见的翻车方式，通常有这几种：

• 你会背模板，但说不清路径、选择列表、结束条件分别是什么。
• 你知道要递归，却讲不清为什么这里要start，那里又要used[]。
• 你把“撤销选择”当成模板动作在机械执行，没理解它为什么是恢复现场的必要步骤。

如果你现在处在“看题知道大概是回溯，但一写就容易乱”的阶段，这一类题特别值得单独练透。读完这篇，你至少要把 3 件事练熟：先把题目翻译成搜索树、先判断它是组合/排列/子集哪一类、能在面试里解释为什么这一步必须撤销选择。

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]的子集题举例，假设当前从空路径开始：

这张表最重要的不是具体答案，而是你要看清楚：回溯并不是“瞎试”，而是在一条路径上向下探索，走不下去或者收集完结果后，再退回来尝试下一个选择。

2. 这类题在面试里考什么

回溯题真正考的不是你能不能背出模板，而是你能不能把题目抽象成搜索树，并且稳定地控制状态。

面试官通常会看：

• 你能不能把题目翻译成路径、选择列表、结束条件。
• 你能不能区分组合、排列、子集这几种搜索树。
• 你是否理解start和used[]分别在控制什么。
• 你会不会在递归回来后恢复现场，避免状态污染。

真正的区分度在于：你不只是把代码写出来，还能解释为什么当前这条分支该继续、为什么另一条分支不能复用刚才的状态。

3. 高频题清单

4. 这类题最容易犯的 3 个错误

1. 只会套模板，讲不出路径、选择列表和结束条件。
2. 递归回来后忘了撤销选择，导致同层分支互相污染。
3. 组合、排列、子集混着写，不知道什么时候该用start，什么时候必须用used[]。

5. 代表题精讲 1

题目

77. 组合

思路

这题要从1..n中选出k个数。每次选完一个数后，后续只能从更大的数继续选，因此它是一道非常标准的组合问题。

你可以把它想成这样一棵树：

• 第一层决定第 1 个数选谁。
• 第二层决定第 2 个数选谁。
• 每往下一层，候选范围都要从当前数后面开始，避免重复。

这里最关键的不是代码，而是这个start参数。它的作用不是“模板规定要传”，而是告诉下一层：前面已经选过的数，不要再回头选了。

Java 代码

importjava.util.ArrayList;importjava.util.List;classSolution{privatefinalList<List<Integer>>result=newArrayList<>();privatefinalList<Integer>path=newArrayList<>();publicList<List<Integer>>combine(intn,intk){backtrack(1,n,k);returnresult;}privatevoidbacktrack(intstart,intn,intk){if(path.size()==k){result.add(newArrayList<>(path));return;}for(inti=start;i<=n;i++){path.add(i);backtrack(i+1,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{privatefinalList<List<Integer>>result=newArrayList<>();privatefinalList<Integer>path=newArrayList<>();privateboolean[]used;publicList<List<Integer>>permute(int[]nums){used=newboolean[nums.length];backtrack(nums);returnresult;}privatevoidbacktrack(int[]nums){if(path.size()==nums.length){result.add(newArrayList<>(path));return;}for(inti=0;i<nums.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(inti=start;i<nums.length;i++){path.add(nums[i]);backtrack(i+1,nums);path.remove(path.size()-1);}

为什么要先收集：因为子集允许长度为0、1、2...n的所有路径，所以当前节点本身就已经代表一个合法答案了。

17. 电话号码的字母组合

这题的路径是当前拼出来的字符串，选择列表来自当前数字对应的字符映射。和组合题不同，它不是在数组里选元素，而是在每一层根据一位数字去扩展字符。

边界上最容易漏的是空字符串输入：digits为空时，应该直接返回空结果，而不是返回包含空串的列表。

8. 回溯题先判断什么

真正动手写之前，你可以先问自己 4 个问题：

1. 这题的路径里到底保存的是什么。
2. 这一层还能从哪些候选里继续选。
3. 我是在什么时候收集答案，是叶子节点还是每个节点。
4. 当前这题需要start控制范围，还是需要used[]控制是否已使用。

这 4 个问题一旦先问清楚，回溯题大部分“写着写着就乱”的情况都会明显减少。

9. 错题本记录方式

回溯题建议重点记录：

• 这题的路径是什么。
• 这题的选择列表是什么。
• 结束条件到底是什么。
• 收集答案的时机在叶子节点还是中间节点。
• 这题为什么要start，或者为什么必须要used[]。

10. 面试前 3 分钟速记

• 回溯先说：路径、选择列表、结束条件。
• 组合：从start往后选，避免重复。
• 排列：每层都能从所有元素里选，但要used[]。
• 子集：通常每个节点都能收集答案。
• 撤销选择不是装样子，而是在恢复现场。

11. 最后总结：回溯真正难的不是模板，而是搜索树视角

如果你只能记住一句话，那就是：回溯题最怕的不是不会写模板，而是你根本没先想清楚当前这道题的搜索树长什么样。

面试时你只要按这个顺序去讲，思路就会稳很多：

1. 先说明路径里保存什么。
2. 再说明这一层还能从哪些候选里选。
3. 接着说答案是在什么时候收集。
4. 最后补一句当前这题为什么该用start或used[]。

这样你就不只是会背add -> recurse -> remove，而是真的掌握了回溯题的公共骨架。

上期速递：【Java实习面试算法冲刺】二分

感谢阅读，记得点赞、关注、收藏，欢迎各位评论区交流！！！