回溯算法：从状态树到剪枝

如果只看定义，“回溯算法：从状态树到剪枝”并不一定显得难。我当时真正卡住的是：回溯最开始给我的感觉就是暴力枚举加递归，直到我把选择过程画成状态树，才知道剪枝到底剪掉了什么。这次整理没有刻意追求一次讲完所有技巧，而是把我最容易断掉的几个理解环节重新接上。

回溯算法解决的是“在很多选择中找满足条件的答案”。它常见于排列、组合、子集、棋盘、字符串拆分和搜索路径问题。

回溯不是简单暴力。暴力是把所有可能都试一遍；回溯是在试的过程中维护状态，并且尽早剪掉不可能成功的分支。

它从哪里来

回溯法在二十世纪五十年代的组合搜索中逐渐形成并获得名称。它把所有选择组织成状态树，走不通就撤销最近选择。剪枝不是额外花招，而是利用约束提前证明某棵子树不可能产生答案。

回溯的状态树

回溯状态树

图：回溯在状态树上选择、进入、撤销和剪枝

一个回溯问题通常可以看成一棵树：

每一层代表一个决策位置。
每条边代表一个选择。
从根到叶子是一种完整方案。
不符合条件的分支可以提前剪掉。

回溯模板

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        收集答案;
        return;
    }

    for (选择 : 选择列表) {
        if (选择不合法) continue;
        做选择;
        backtrack(路径, 新的选择列表);
        撤销选择;
    }
}

这段模板的重点不是形式，而是三个动作：

做选择。
进入下一层。
撤销选择。

撤销选择很关键，因为同一个路径对象通常会被复用。如果不撤销，兄弟分支会互相污染。

子集问题

给定数组，生成所有子集。

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    dfs(nums, 0, path, ans);
    return ans;
}

void dfs(int[] nums, int start, List<Integer> path, List<List<Integer>> ans) {
    ans.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        dfs(nums, i + 1, path, ans);
        path.remove(path.size() - 1);
    }
}

这里 start 保证每个元素只往后选择，避免重复。

排列问题

排列和子集不同：每个位置都可以选择尚未使用的元素。

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    dfs(nums, used, new ArrayList<>(), ans);
    return ans;
}

void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
    if (path.size() == nums.length) {
        ans.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        dfs(nums, used, path, ans);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

这里 used 维护当前路径中哪些元素已经被使用。

组合问题与剪枝

组合问题通常不关心顺序。比如从 1..n 里选 k 个数：

void combine(int n, int k, int start, List<Integer> path, List<List<Integer>> ans) {
    if (path.size() == k) {
        ans.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i <= n - (k - path.size()) + 1; i++) {
        path.add(i);
        combine(n, k, i + 1, path, ans);
        path.remove(path.size() - 1);
    }
}

循环终点 n - (k - path.size()) + 1 就是剪枝：如果剩余数字已经不够凑满 k 个，就没必要继续枚举。

回溯和 DFS 的关系

DFS 是一种遍历方式，回溯是一种搜索策略。回溯通常用 DFS 实现，但比普通 DFS 多了“选择、撤销、剪枝”的状态管理。

例如树的 DFS 只是访问节点；N 皇后回溯则要维护列、对角线是否被占用，并在失败后撤销。

常见错误

收集答案时没有拷贝路径，导致最后答案全一样。
忘记撤销选择。
start 使用错误，导致组合重复。
排列去重时没有排序和跳过同层重复。
剪枝条件写得太激进，把正确答案剪掉。
递归终止条件不完整。

工程场景

回溯在业务系统里不如哈希表、队列那样常见，但思想很有用：

权限组合搜索。
规则引擎匹配。
排班和资源分配。
配置方案生成。
路径规划中的候选方案搜索。
测试用例组合生成。

工程里要非常警惕搜索爆炸。回溯适合规模可控的问题；如果规模很大，必须加入剪枝、缓存、启发式排序，甚至改成动态规划、贪心或约束求解。

面试题

回溯为什么要撤销选择？
子集、组合、排列的区别是什么？
如何避免组合问题出现重复答案？
剪枝为什么可能影响正确性？
回溯和动态规划有什么关系？

小结

回溯的核心不是模板，而是状态树。你要知道每一层在做什么选择，路径里保存什么状态，什么时候收集答案，什么时候撤销，什么时候剪枝。能把这棵树画清楚，代码自然就顺了。