回溯算法
回溯是面试中最考察"思维框架"的算法。关键不是背代码，而是理解递归决策树和如何枚举所有可能。
面试考察点
面试官通过这道题想考察：
1. 你是否能画出问题的递归决策树
2. 你是否能正确实现"选择"和"撤销选择"
3. 你是否能进行剪枝优化
4. 你是否能区分回溯和 DFS/BFS
一、回溯的本质
1.1 什么是回溯？（小白解释）
面试官追问："什么是回溯？为什么叫回溯？"
回溯 = 枚举 + 撤销
想象走迷宫：
1. 选一条路走
2. 走到死路 → 回退到上一个路口
3. 选另一条路
4. 重复直到找到出口
这不就是"回退" + "继续探索" = 回溯！
回溯的关键词：
- 选择：做一件事
- 撤销：把这件事 undo
- 继续：尝试下一个选择
1.2 回溯的决策树（核心）
面试官追问："怎么理解回溯的递归决策树？"
以"生成括号"为例：n=3
递归决策树：
""
├── "("
│ ├── "(( "
│ │ ├── "(((" → 添加 ")" → "((())"
│ │ └── ...
│ └── "(("
│ └── ...
└── ...
每一步都有选择：
- 可以加左括号（如果还有）
- 可以加右括号（如果左括号数 > 右括号数）
叶子节点 = 完整解
1.3 回溯的通用模板
def backtrack(路径, 选择列表):
if 满足结束条件:
结果.add(路径)
return
for 选择 in 选择列表:
# 做选择
路径.add(选择)
做选择(选择列表)
# 回溯（撤销选择）
路径.remove(选择)
撤销选择(选择列表)
二、子集问题
2.1 问题：求所有子集
考察点：最基本的回溯
问题：求数组 [1,2,3] 的所有子集
决策树：
[] (空集)
/ | \
1 2 3
/| | |
12 13 23 (只有叶子节点是解？错！)
正确决策树：
[] 根节点也是子集！
/ \
1 (跳过1)
/ \
12 (跳过2)
/
123
所有节点都是子集！
结果：[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]
2.2 去重技巧
问题：有重复元素时如何去重？
示例：[1,1,2]
关键：相同元素，前一个没用过就不能用后一个
排序后：
[1,1,2]
决策时跳过重复：
if i > start and nums[i] == nums[i-1]: continue
三、排列问题
3.1 全排列
考察点：回溯 + 标记
问题：求 [1,2,3] 的全排列
决策树：
[]
/ | \
1 2 3
/| /| /|
12 21 13 31 23 32 ← 叶子节点
关键：需要一个 used 数组标记已使用的元素
3.2 全排列 II（去重）
问题：有重复元素的全排列
排序后，相同元素相邻
去重条件：
if used[i-1] == false: continue
// 解释：前一个相同元素没有被用过，所以跳过
四、面试真题讲解
4.1 括号生成（LeetCode 22）
考察点：回溯的应用
问题：生成 n 对括号的所有有效组合
思路：
- 左括号随时可以加（如果有剩余）
- 右括号只能在左括号比右括号多时加
递归决策：
def backtrack(path, left, right):
if left == right == n:
结果.add(path)
return
# 可以加左括号
if left < n:
backtrack(path + '(', left + 1, right)
# 可以加右括号
if left > right:
backtrack(path + ')', left, right + 1)
4.2 N 皇后（LeetCode 51）
考察点：回溯 + 约束检测
问题：在 N×N 棋盘上放 N 个皇后，不能互相攻击
约束：
- 同一行只能有一个皇后
- 同一列只能有一个皇后
- 对角线只能有一个皇后
回溯思路：
逐行放置，检查当前位置是否安全
如果不安全就回退
五、面试总结
回溯的核心
┌─────────────────────────────────────────────────┐
│ 回溯算法 │
├─────────────────────────────────────────────────┤
│ │
│ 本质：枚举 + 撤销 │
│ │
│ 三要素： │
│ 1. 路径：已经做的选择 │
│ 2. 选择列表：当前可以做的选择 │
│ 3. 结束条件：到达叶子节点 │
│ │
│ 优化： │
│ - 剪枝：提前判断不合法的情况 │
│ - 去重：排序后跳过重复 │
│ │
│ 应用： │
│ - 子集问题 │
│ - 排列问题 │
│ - 组合问题 │
│ │
└─────────────────────────────────────────────────┘
面试能加分的回答
1. 能画出递归决策树
"回溯的问题都可以用递归决策树表示"
2. 能正确实现撤销操作
"撤销是回溯的灵魂，必须正确实现"
3. 能进行剪枝优化
"提前判断不合法情况，减少搜索空间"
相关题目
- LeetCode 78 - 子集 - 子集问题
- LeetCode 46 - 全排列 - 排列问题
- LeetCode 22 - 括号生成 - 回溯应用
- LeetCode 51 - N 皇后 - 回溯进阶