回溯
本章题海战术
| 典型例题 | leetcode题目 | leetcode链接 |
|---|---|---|
| 组合 | leetcode 77 | https://leetcode.cn/problems/combinations/description/ |
| 子集 | leetcode 78 | https://leetcode.cn/problems/subsets/description/ |
| 全排列 | leetcode 46 | https://leetcode.cn/problems/permutations/description/ |
| 全排列 II | leetcode 47 | https://leetcode.cn/problems/permutations-ii/description/ |
| 子集 II | leetcode 90 | https://leetcode.cn/problems/subsets-ii/description/ |
| 组合总和 | leetcode 39 | https://leetcode.cn/problems/combination-sum/description/ |
| 组合总和 II | leetcode 40 | https://leetcode.cn/problems/combination-sum-ii/description/ |
| 分割回文串 | leetcode 131 | https://leetcode.cn/problems/palindrome-partitioning/description/ |
| 复原 IP 地址 | leetcode 93 | https://leetcode.cn/problems/restore-ip-addresses/description/ |
| N 皇后 | leetcode 51 | https://leetcode.cn/problems/n-queens/description/ |
| 解数独 | leetcode 37 | https://leetcode.cn/problems/sudoku-solver/description/ |
回溯
面试现场回答（模拟真实场景）
面试官您好，关于回溯算法，我是这么理解的：
回溯本质是带「撤销操作」的深度优先搜索，专门解决排列、组合、子集、分割、棋盘这类需要枚举所有合法解的问题。它的核心套路非常固定，所有题目都遵循「做选择 → 递归下一层 → 撤销选择」的三段式框架，区别只在于终止条件、选择范围和剪枝逻辑不同。
下面我结合 5 道面试最高频的经典题，具体拆解解题思路和代码实现。
回溯核心模型与通用模板 💡
回溯的底层是一棵决策树：每一层对应一次选择，每个节点对应当前路径状态，叶子节点对应合法解。算法遍历整棵树，遇到合法解就收集，遇到死路就回退换分支。
通用代码骨架（面试万能模板）
class Solution {
List<List<Integer>> res = new ArrayList<>(); // 存放所有合法结果
LinkedList<Integer> path = new LinkedList<>(); // 记录当前决策路径
public List<List<Integer>> mainFunc(int[] nums) {
// 预处理：排序（去重题必备）、初始化标记数组等
backtrack(nums, 0); // 0一般是起始索引/层数
return res;
}
private void backtrack(int[] nums, int startIndex) {
// 1. 终止条件：满足题目要求，收集结果并返回
if (终止条件) {
res.add(new ArrayList<>(path));
return;
}
// 2. 遍历当前层的选择列表
for (int i = startIndex; i < nums.length; i++) {
// 3. 剪枝：不合法的分支直接跳过（去重、越界、不满足约束等）
if (剪枝条件) continue;
// 4. 做选择
path.add(nums[i]);
// 5. 递归进入下一层决策
backtrack(nums, 下一层的起始索引);
// 6. 回溯撤销选择（和选择严格成对出现）
path.removeLast();
}
}
}✨ 模板核心原则：选择与撤销必须成对，递归前后状态完全一致，这是回溯不出错的根本。
高频经典题详细拆解 📌
1. 入门必考题：LeetCode 77. 组合
题意：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
核心考点：组合类问题的startIndex思想，解决组合不重复的问题。
决策树图解（以 n=4, k=2 为例）
解题思路
组合的核心特点是无序（[1,2]和[2,1]是同一个结果），因此每层递归必须从startIndex开始向后选，不能回头选前面的元素，天然避免重复。
Java 代码实现
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
backtrack(n, k, 1);
return res;
}
private void backtrack(int n, int k, int startIndex) {
// 终止条件：路径长度等于k，收集结果
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
// 剪枝优化：剩余元素数量不足时直接跳过
// 还需要选 k - path.size() 个元素，i最大到 n - (k - path.size()) + 1
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
// 做选择
path.add(i);
// 下一层从i+1开始，不重复选当前元素
backtrack(n, k, i + 1);
// 撤销选择
path.removeLast();
}
}
}面试技术亮点
- 用
startIndex控制选择范围，一行代码解决组合去重，是组合 / 子集类题的核心标志 - 剩余元素剪枝：提前判断剩余元素是否足够，减少无效递归，面试写出属于加分项
2. 高频坑题：LeetCode 47. 全排列 II
题意：给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。
核心考点：同层去重原理，面试 90% 会追问去重逻辑细节。
去重核心原理
数组先排序，让重复元素相邻；同一树层中，遇到和前一个相同的元素，且前一个未被使用，说明是同层重复，直接跳过。
!used[i-1]：前一个元素未被使用 → 同层重复，必须跳过used[i-1]：前一个元素已被使用 → 同枝重复，属于合法情况
Java 代码实现
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
used = new boolean[nums.length];
Arrays.sort(nums); // 去重前提：排序让重复元素相邻
backtrack(nums);
return res;
}
private void backtrack(int[] nums) {
// 终止条件：路径长度等于数组长度
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
// 1. 当前元素已被使用，跳过
if (used[i]) continue;
// 2. 同层去重：和前一个元素相同，且前一个未被使用（同层重复）
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
// 做选择
used[i] = true;
path.add(nums[i]);
// 递归下一层
backtrack(nums);
// 撤销选择
path.removeLast();
used[i] = false;
}
}
}面试技术亮点
- 排序 + 同层去重，是解决重复元素回溯题的工业级标准方案
- 能讲清
!used[i-1]和used[i-1]的区别，说明对回溯树的层与枝理解到位，是面试拉开差距的关键点
3. 高频变形题：LeetCode 39. 组合总和
题意：给你一个无重复元素的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
核心考点：元素可重复选取的索引控制、求和剪枝优化。
解题思路
- 元素可重复选 → 下一层递归传i而不是
i+1，允许继续选当前元素 - 数组先升序排序，当当前元素加入后已经超过剩余目标值时，后面的元素更大，直接
break剪枝
Java 代码实现
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates); // 排序用于后续剪枝
backtrack(candidates, target, 0, 0);
return res;
}
// sum：当前路径的元素和
private void backtrack(int[] candidates, int target, int sum, int startIndex) {
// 终止条件：和等于target，收集结果
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
// 剪枝：当前元素加入后超过target，后面元素更大，直接break
if (sum + candidates[i] > target) break;
// 做选择
path.add(candidates[i]);
sum += candidates[i];
// 关键点：传i而不是i+1，允许重复选当前元素
backtrack(candidates, target, sum, i);
// 撤销选择
sum -= candidates[i];
path.removeLast();
}
}
}面试技术亮点
- 索引传
i实现元素重复选取，是这道题的核心区分点 - 排序后用
sum + candidates[i] > target做剪枝，大幅减少递归次数，性能提升明显
4. 分割类代表：LeetCode 131. 分割回文串
题意：给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
核心考点：切割线思想，将陌生的分割问题转化为熟悉的组合模型。
解题思路
把切割线的位置当作选择对象：startIndex就是切割线的位置，每次在[startIndex, i]区间截取子串，判断是否是回文，是就加入路径，继续向后切割。
Java 代码实现
class Solution {
List<List<String>> res = new ArrayList<>();
LinkedList<String> path = new LinkedList<>();
public List<List<String>> partition(String s) {
backtrack(s, 0);
return res;
}
private void backtrack(String s, int startIndex) {
// 终止条件：切割线走到字符串末尾，说明所有子串都是回文，收集结果
if (startIndex == s.length()) {
res.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < s.length(); i++) {
// 判断[startIndex, i]区间的子串是否是回文
if (!isPalindrome(s, startIndex, i)) continue;
// 做选择：截取子串加入路径
path.add(s.substring(startIndex, i + 1));
// 下一层切割线从i+1开始
backtrack(s, i + 1);
// 撤销选择
path.removeLast();
}
}
// 双指针判断回文串
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) return false;
left++;
right--;
}
return true;
}
}面试技术亮点
- 用
startIndex抽象切割线，把分割问题转化为组合模型，是这类题的核心破题思路 - 双指针原地判断回文，不额外生成子串，空间效率更高
5. 困难压轴题：LeetCode 51. N 皇后
题意：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击（同一行、同一列、同一斜线都不能有其他皇后）。
核心考点：二维棋盘约束、逐层递归降维、全局合法性校验。
解题思路
按行递归，每行只放一个皇后，每一层枚举当前行的所有列，判断该位置是否合法（列、左上斜线、右上斜线无皇后），合法就放置，递归下一行。
Java 代码实现
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
// 初始化棋盘，用char数组方便修改
char[][] chessboard = new char[n][n];
for (char[] row : chessboard) {
Arrays.fill(row, '.');
}
backtrack(chessboard, 0, n);
return res;
}
// row：当前处理到第几行
private void backtrack(char[][] chessboard, int row, int n) {
// 终止条件：所有行都放完了，收集结果
if (row == n) {
res.add(arrayToList(chessboard));
return;
}
// 遍历当前行的每一列
for (int col = 0; col < n; col++) {
// 剪枝：当前位置不合法，跳过
if (!isValid(chessboard, row, col, n)) continue;
// 做选择：放置皇后
chessboard[row][col] = 'Q';
// 递归处理下一行
backtrack(chessboard, row + 1, n);
// 撤销选择
chessboard[row][col] = '.';
}
}
// 判断(row, col)位置是否可以放皇后
private boolean isValid(char[][] chessboard, int row, int col, int n) {
// 1. 检查同一列
for (int i = 0; i < row; i++) {
if (chessboard[i][col] == 'Q') return false;
}
// 2. 检查左上斜线
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (chessboard[i][j] == 'Q') return false;
}
// 3. 检查右上斜线
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (chessboard[i][j] == 'Q') return false;
}
return true;
}
// 棋盘数组转结果列表
private List<String> arrayToList(char[][] chessboard) {
List<String> list = new ArrayList<>();
for (char[] row : chessboard) {
list.add(new String(row));
}
return list;
}
}面试技术亮点
- 按行递归降维：把二维问题转化为一维的逐行决策，大幅降低复杂度
- 只检查上方区域：因为是从上往下放皇后，下方还没放，无需检查，减少一半判断量
- 棋盘用 char 数组存储，修改和转换都高效，是字符串棋盘题的标准写法
技术难点与解决方案汇总 ⚠️
| 技术难点 | 问题场景 | 解决方案 |
|---|---|---|
| 重复结果生成 | 数组含重复元素的排列 / 组合 / 子集题 | 先排序使重复元素相邻，同层去重：i > start && nums[i] == nums[i-1] && !used[i-1]时跳过 |
| 组合排列混淆 | 组合题写出排列结果，出现重复逆序对 | 组合 / 子集题必须传startIndex，每层从前往后选；排列题从 0 开始遍历，配合 used 数组 |
| 剪枝时机错误 | 剪枝放在递归之后，无效递归已执行 | 剪枝前置到「做选择」之前，不满足条件直接 continue/break，不进入递归 |
| 撤销选择遗漏 | 路径状态污染，后续分支携带多余元素 | 严格遵循「选择 - 递归 - 撤销」三段式，撤销操作紧跟递归，成对编写 |
| 分割问题无从下手 | 字符串分割、IP 复原等题 | 用startIndex抽象切割线，每次截取[startIndex, i]区间，转化为组合模型 |
| 棋盘类约束复杂 | N 皇后、数独等二维问题 | 按行 / 按格逐层递归，每一层只处理一个位置，提前封装合法性校验函数 |
LeetCode 高频面试题清单 📋
| 难度 | 题号 | 题目名称 | 题型分类 |
|---|---|---|---|
| 入门 | 77 | 组合 | 组合基础 |
| 入门 | 78 | 子集 | 子集基础 |
| 高频中等 | 46 | 全排列 | 排列基础 |
| 高频中等 | 47 | 全排列 II | 排列 + 去重 |
| 高频中等 | 90 | 子集 II | 子集 + 去重 |
| 高频中等 | 39 | 组合总和 | 组合 + 重复选取 |
| 高频中等 | 40 | 组合总和 II | 组合 + 去重 |
| 高频中等 | 131 | 分割回文串 | 分割类 |
| 高频中等 | 93 | 复原 IP 地址 | 分割 + 边界校验 |
| 困难 | 51 | N 皇后 | 棋盘类 |
| 困难 | 37 | 解数独 | 棋盘类 + 提前返回 |
真实面试模拟
真实面试模拟
面试官：
😄 同学你好，我是今天的面试官。
咱们先不着急做题，你先简单说说，你怎么理解“回溯算法”？一句话概括也行。
候选人：
好的面试官。
我觉得回溯本质上就是 在隐式的多叉树上做深度优先搜索，核心思想是“试错”——选择一条路走到底，走不通就撤销，退回换条路再走。
所有回溯问题都可以抽象成三个部分：
- 路径（已经做过的选择）
- 选择列表（当前还能选什么）
- 结束条件（什么时候算一条合法路径，需要收割结果）
面试官：
嗯，概括得挺准。那如果让你写一个通用代码骨架，你会怎么写？
候选人：
没问题，我先给一个 Java 版的通用框架：
void backtrack(路径, 选择列表) {
if (满足结束条件) {
result.add(new ArrayList<>(路径)); // 🎯 收割结果，注意拷贝
return;
}
for (选择 : 选择列表) {
做选择; // 将选择加入路径
backtrack(路径, 新选择列表); // 下探
撤销选择; // ⏪ 回溯，状态恢复
}
}所有的排列、组合、子集、切割、棋盘问题，都是在这个骨架上调整 选择列表的维护方式 和 剪枝/去重条件。
面试官：
骨架有了，那咱们落地一下，讲一下 全排列（LeetCode 46） 吧，你怎么用这个框架解？
候选人：
好的。全排列问题是回溯最经典的例子，我们来画一棵决策树。
以数组 [1,2,3] 为例：
[]
/ | \
1 2 3
/ \ / \ / \
2 3 1 3 1 2
/ \ / \ / \
3 2 3 1 2 1- 路径：当前已经排好的数字，比如
[1] - 选择列表：剩下的还没用过的数字，用
boolean[] used标记 - 结束条件：路径长度等于数组长度，就收获一个全排列
核心代码：
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length];
backtrack(nums);
return res;
}
void backtrack(int[] nums) {
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);
path.removeLast(); // ⬅️ 撤销
used[i] = false;
}
}
}时间复杂度 O(n!)，空间 O(n) 递归栈。
面试官：
很好。那如果数组里有重复元素呢？比如 [1,1,2]，怎么避免结果集重复？
这就是 全排列 II（LeetCode 47） 了对吧？
候选人：
对，这道题是去重的典型题。
核心思路：先排序，再同层去重。
去重的条件写出来是：
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;为什么用 !used[i - 1]？
假设数组排序后为 [1₁, 1₂, 2]，决策树片段是：
[ ]
/ 选择1₁ \选择1₂ ...
[1₁] [1₂]
/ \ / \
[1₁,1₂] [1₁,2] [1₂,1₁] ❌ 重复！当 !used[i-1] 为真时，说明前一个相同元素 没有在当前路径被使用，那它俩在同一层是兄弟关系，应该跳过，否则会产生重复分支。
修改后的代码：
Arrays.sort(nums);
void backtrack(int[] nums) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // ⚡同层去重
used[i] = true;
path.add(nums[i]);
backtrack(nums);
path.removeLast();
used[i] = false;
}
}面试官：
嗯，这个 !used[i-1] 解释得很清楚。那组合问题呢？比如 子集 II（LeetCode 90），去重条件是不是差不多？
候选人：
对，但组合 / 子集不需要考虑顺序，所以选择列表用 start 下标控制，天然避免了不同顺序的重复。
去重条件变成：同一递归层内，若 i > start && nums[i] == nums[i-1]，则跳过。
为啥是 i > start 而不是 i > 0？
因为 start 是本层第一个可选位置，我们要保证“同一层不能重复选相同的值”，但允许递归下层时选到同样的值，所以用 i > start 精准控制。
核心代码：
void backtrack(int[] nums, int start) {
res.add(new ArrayList<>(path)); // 每个节点都收割
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) continue; // 同层去重
path.add(nums[i]);
backtrack(nums, i + 1);
path.removeLast();
}
}面试官：
这是去重。那剪枝呢？拿 组合总和 II（LeetCode 40） 来说说，怎么减少无效搜索？
候选人：
组合总和 II 既是去重又是剪枝的好例子。
候选数组排序后，我们可以在循环里做两个优化：
- 同层去重：
if (i > start && cand[i] == cand[i-1]) continue; - 剪枝：因为升序，如果当前数
cand[i] > target，那后面的数更大，直接break终止循环。
关键代码片段：
void backtrack(int[] cand, int target, int start) {
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < cand.length; i++) {
if (i > start && cand[i] == cand[i - 1]) continue; // 去重
if (cand[i] > target) break; // 🪓 剪枝
path.add(cand[i]);
backtrack(cand, target - cand[i], i + 1); // 每个数只用一次
path.removeLast();
}
}这样能大幅减少递归分支，尤其在 target 很小的时候效果明显。
面试官：
好的。前面几题都是选择元素，那 切割问题 呢？比如 分割回文串（LeetCode 131），你怎么建模成回溯？
候选人：
切割问题本质上是 枚举切割点。
我们把切割线用 start 索引表示，每一层递归都是从 start 开始尝试切一刀，如果切出来的子串是回文，就下探到 i+1 继续切剩余部分，直到把整个字符串切完。
决策树（s = "aab"）可以画成：
start=0
┌──────┼──────┐
"a" "aa" "aab"❌(非回文)
start=1 start=2
┌──┼──┐ │
"a" "ab" "b"
│ ❌ end
"b"
end核心代码：
void backtrack(String s, int start) {
if (start == s.length()) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < s.length(); i++) {
if (!isPalindrome(s, start, i)) continue; // 剪枝
path.add(s.substring(start, i + 1));
backtrack(s, i + 1);
path.removeLast();
}
}回文判断还可以用记忆化或者动态规划预处理，进一步优化。
面试官：
那二维棋盘约束问题，比如 N 皇后（LeetCode 51），回溯怎么玩？
候选人：
N 皇后是典型的 按行递归 问题。
我们把递归深度 row 当作行号，每一层循环遍历列，尝试在 (row, col) 放置皇后，然后检查是否冲突。冲突约束用三个集合来记录：
cols：哪些列被占用diag1：左上-右下斜线，特征row - col恒定diag2：右上-左下斜线，特征row + col恒定
只要不冲突就递归下一行，回溯时撤销占用。
核心片段：
void backtrack(int row) {
if (row == n) {
res.add(constructBoard());
return;
}
for (int col = 0; col < n; col++) {
if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col))
continue;
placeQueen(row, col);
cols.add(col); diag1.add(row - col); diag2.add(row + col);
backtrack(row + 1);
cols.remove(col); diag1.remove(row - col); diag2.remove(row + col);
removeQueen(row, col);
}
}时间复杂度理论上是 O(N!)，但实际剪枝效果很好。
面试官：
聊下来感觉你对回溯套路挺熟的，最后能不能用一张表总结一下 常见的技术难点和解决方案？
候选人：
当然可以，我整理一下：
| 难点 | 解决方案 | 常犯错误 |
|---|---|---|
| 重复元素去重 | 排序 + 同层跳过。排列用 !used[i-1]；组合/子集用 i > start && nums[i]==nums[i-1] | 树枝去重当成同层去重，漏解 |
| 剪枝减少分支 | 排序后 if (cand[i] > target) break；合法性判断前置（回文/冲突） | 忘记剪枝导致超时 |
| 结果集拷贝 | res.add(new ArrayList<>(path)) | 直接传引用，结果被篡改 |
| 状态恢复 | 递归前后对称操作（add/remove，used=true/false） | 只做选择忘撤销，path无限增长 |
| 选择列表维护 | 用 start 下标或 used 数组 O(1) 判断 | 用 contains() 导致 O(n²) |
| 复杂度分析 | 排列 O(n!)，组合/子集 O(2^n)，可剪枝降低常数 | 被问住可先给上界，再解释剪枝 |
面试官：
非常清晰。那我最后问一个工程相关的：回溯递归层次太深可能导致栈溢出，你怎么看？
候选人：
好的，这个问题实际但不太常见。
回溯深度通常等于输入规模，比如数组长度或者棋盘大小，LeetCode 题目的输入一般不会大到让 JVM 栈溢出（默认栈约 1MB）。
如果真遇到深度很大的场景（比如超长字符串切割），可以考虑两个优化方向：
- 剪枝：尽可能减少递归分支，让递归深度实际变浅。
- 迭代 + 显式栈：把递归改写为手动维护一个栈结构，虽然代码复杂些，但可以避免系统栈限制。
不过面试中，首先还是强调剪枝优化，因为迭代改写可读性较差，并不是首选。
面试官：好的，整体回答得很扎实，回溯这块你应该没什么问题了。👍
候选人：谢谢面试官，我会继续巩固剪枝和建模的细节。😊