回溯算法（Backtracking）
回溯算法是「遍历」思维模式的典型应用：在递归树上遍历所有可能的选择，到达叶子节点时收集结果，不合适时撤销选择（回溯）。
定义
回溯算法（Backtracking）是一种通过试错来寻找问题解的算法范式。它在递归树上进行深度优先搜索，尝试一条路径，遇到不合适的情况时撤销上一步的选择（回溯），继续尝试其他路径。
核心本质：回溯算法 = 递归遍历 + 做选择 + 撤销选择
决策树视角
回溯算法本质是遍历一棵决策树的过程（参见 回溯算法框架）：
- 路径：记录已经做出的选择
- 选择列表：当前可以做的选择
- 结束条件：到达决策树底层叶子节点
关键点：回溯算法和 DFS 算法基本可认为是同一种算法，细微差异在于实现视角。回溯算法强调"做选择→递归→撤销选择"的模式。
核心特性
| 特性 | 说明 |
|---|---|
| 试探性 | 尝试一种选择，看是否能得到解 |
| 可撤销 | 不合适时可以撤销上一步选择 |
| 穷举所有 | 遍历整个递归树（或剪枝后部分） |
| DFS 性质 | 本质是深度优先搜索 |
与递归的关系
回溯算法与递归（遍历思维）的关系：
| 维度 | 普通遍历递归 | 回溯算法 |
|---|---|---|
| 思维模式 | 遍历 | 遍历（带状态管理） |
| 状态管理 | 可能用外部变量 | 必须维护选择路径（track） |
| 操作 | 遍历收集 | 做选择 → 递归 → 撤销选择 |
| 示例 | 简单 DFS | 全排列、N 皇后 |
关键洞察：理解递归的遍历思维是学习回溯算法的前提。回溯算法就是在递归遍历的基础上，加上"做选择"和"撤销选择"的步骤。
标准框架
result = []
void backtrack(路径, 选择列表) {
if (满足结束条件) {
result.add(路径的拷贝)
return
}
for (选择 in 选择列表) {
// 做选择
路径.add(选择)
// 递归进入下一层
backtrack(路径, 选择列表)
// 撤销选择（回溯）
路径.removeLast()
}
}
三个关键点：
- 路径：记录当前已做的选择
- 选择列表：当前还可以做哪些选择
- 结束条件：什么时候收集结果
经典问题
| 问题 | 难度 | 说明 |
|---|---|---|
| 全排列 | 中等 | 回溯入门经典，每个位置尝试所有可选数字 |
| N 皇后 | 困难 | 每行尝试放皇后，检查冲突 |
| 组合 | 中等 | 从 n 个数中选 k 个，不重复 |
| 子集 | 中等 | 每个元素可选可不选，生成所有子集 |
| 单词搜索 | 中等 | 在二维网格中搜索单词，四个方向回溯 |
| 数独求解 | 困难 | 每个空格尝试 1-9，检查合法性 |
全排列：回溯入门
问题：给定不重复的数字数组，返回所有可能的排列。
List<List<Integer>> res = new LinkedList<>();
List<List<Integer>> permute(int[] nums) {
LinkedList<Integer> track = new LinkedList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, track, used);
return res;
}
void backtrack(int[] nums, LinkedList<Integer> track, boolean[] used) {
// 结束条件：路径长度 = 数组长度
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// 排除不合法的选择
if (used[i]) continue;
// 做选择
track.add(nums[i]);
used[i] = true;
// 递归
backtrack(nums, track, used);
// 撤销选择（回溯）
track.removeLast();
used[i] = false;
}
}
递归树理解：全排列的递归树是多叉树，每个节点代表一次选择，叶子节点是一个完整的排列。
剪枝优化
回溯算法可以通过剪枝提高效率：
| 剪枝场景 | 方法 |
|---|---|
| 重复选择 | 用 used 数组或 Set 记录已选元素 |
| 顺序无关 | 记录起始位置，避免重复组合 |
| 约束条件 | 提前判断当前路径是否可能得到解 |
| 可行性 | 如 N 皇后中检查冲突 |
与动态规划的区别
虽然回溯算法和动态规划都抽象为树/图的结构，但两者思路完全不同（参见 回溯算法框架）：
| 维度 | 回溯算法 | 动态规划 |
|---|---|---|
| 抽象模型 | 决策树 | 状态转移图 |
| 核心三要素 | 路径、选择列表、结束条件 | 状态、选择、base case |
| 优化空间 | 无（纯暴力穷举） | 有（记忆化/重叠子问题） |
| 时间复杂度 | 指数级 O(n!)、O(2^n) | 多项式级 O(n²)、O(n³) |
关键区别：回溯算法必须穷举整棵决策树，无法避免指数级复杂度；而动态规划通过记忆化避免重复计算，可以优化到多项式时间。
与贪心算法的区别
回溯算法与贪心算法都用于搜索/优化问题，但策略完全不同（参见 贪心算法解题套路框架）：
| 维度 | 回溯算法 | 贪心算法 |
|---|---|---|
| 优化手段 | 剪枝优化，提前排除不可能的答案 | 推导最优，跳过完整穷举 |
| 穷举范围 | 穷举所有可行解（剪枝后可能部分） | 不穷举所有可行解 |
| 时间复杂度 | 指数级 $O(2^n)$、$O(n!)$ | 通常 $O(n)$ 或 $O(1)$ |
| 正确性保证 | 只要正确穷举就保证找到最优解 | 需要证明贪心选择性质成立 |
| 状态管理 | 需要维护路径，做选择/撤销选择 | 通常不需要回溯，直接选择 |
演进关系：回溯（剪枝优化）→ 动态规划（备忘录优化）→ 贪心（推导最优，不穷举）。每一步都在减少穷举的范围。
时间复杂度
回溯算法通常是指数级时间复杂度，因为要穷举所有可能：
| 问题 | 时间复杂度 | 说明 |
|---|---|---|
| 全排列 | O(n!) | n 个数字的所有排列 |
| 子集 | O(2^n) | 每个元素可选可不选 |
| 组合 C(n,k) | O(C(n,k)) | 从 n 个选 k 个 |
注意事项
- 要撤销选择：递归返回后必须恢复状态，否则路径会累积错误
- 要拷贝结果：加入结果集时要拷贝路径，不能加入引用
- 剪枝要早：尽早排除不可能的路径，减少搜索空间
- 递归深度：深度过大可能栈溢出，注意边界
应用场景
- 组合枚举：全排列、组合、子集
- 约束满足：N 皇后、数独、图的着色
- 路径搜索：单词搜索、迷宫问题
- 决策问题：0-1 背包（带剪枝）
相关概念
- 递归：回溯算法的基础，遍历思维
- DFS：回溯算法本质是深度优先搜索
- 分治算法：也用递归，但不需要回溯（子问题独立）
- 动态规划：带记忆化的分解问题，与回溯思路不同
- 贪心算法：比回溯更进一步，不穷举所有可行解
- 二叉树：回溯算法的递归树类似多叉树
参考资料
- 理解递归框架：回溯算法是遍历思维的体现
- 算法总结：算法框架思维总结
- 回溯算法框架：回溯算法决策树模型与通用框架
- 排列组合子集问题一网打尽：排列/组合/子集问题的9种形式与回溯树