回溯算法框架
核心思想
回溯算法本质是遍历一棵决策树的过程，树的每个叶子节点存放着一个合法答案。把整棵树遍历一遍，收集所有叶子节点的答案，就得到所有合法答案。
回溯算法与 DFS 算法基本可认为是同一种算法，细微差异在于实现视角（参见DFS与回溯算法的关系）。
回溯算法的三个关键问题
站在回溯树的某个节点上，需要思考 3 个问题：
- 路径：已经做出的选择
- 选择列表：当前可以做的选择
- 结束条件：到达决策树底层，无法再做选择的条件
算法框架
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
核心：for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」。
全排列问题详解
以 LeetCode 46（全排列）为例，输入数组 nums，返回所有数字的全排列。
决策树模型
全排列问题可以抽象为一棵决策树（回溯树）：
站在树的某个节点上（红色节点）：
每个节点的属性（路径、选择列表）：
前序遍历和后序遍历的时间点：
在递归前后做选择和撤销选择：
使用 used 数组推导选择列表：
总结：
- 路径
[2]：记录已经做过的选择 - 选择列表
[1, 3]：当前可以做的选择 - 结束条件：选择列表为空（或路径长度等于数组长度）
代码实现（Java）
class Solution {
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; // nums[i] 已经在 track 中，跳过
}
// 做选择
track.add(nums[i]);
used[i] = true;
// 进入下一层决策树
backtrack(nums, track, used);
// 取消选择
track.removeLast();
used[i] = false;
}
}
}
关键点
- 使用
used数组记录已选择的元素，推导出当前的选择列表 - 时间复杂度：O(n!)，必须穷举整棵决策树
- 回溯算法是纯暴力穷举，不像动态规划存在重叠子问题可以优化
与动态规划的关系
| 维度 | 回溯算法 | 动态规划 |
|---|---|---|
| 抽象模型 | 决策树 | 状态转移图 |
| 核心三要素 | 路径、选择列表、结束条件 | 状态、选择、base case |
| 优化空间 | 无（纯暴力穷举） | 有（记忆化/重叠子问题） |