回溯法介绍

一、什么是回溯法

回溯法（Backtracking）是一种 系统地搜索问题所有可能解的算法思想。
它通过 深度优先遍历（DFS） 的方式，不断尝试所有路径，当发现当前路径不满足条件时，立即“回退（backtrack）”到上一步重新选择。

简单来说，回溯法是一种“穷举 + 剪枝”的算法框架，用于解决 组合、排列、子集、路径搜索、数独、八皇后 等问题。

---

二、回溯与“决策树”的关系

所有回溯过程，都可以形象地看成是在一棵“决策树”上进行的搜索。

• 每个节点：表示当前状态（当前的选择路径）。
• 每条分支：表示做出的一个选择。
• 根节点：表示初始状态（什么都还没选择）。
• 叶子节点：表示到达结束条件（形成一个完整的解）。

回溯的过程 = 在决策树上进行 DFS（深度优先遍历）：

• 向下走：做出选择，进入更深层的状态。
• 向上退：撤销选择，尝试下一个可能路径。

例如「全排列」问题，假设输入 [1, 2, 3]：

          []
       /    |    \
     [1]   [2]   [3]
    / \     / \    / \
 [1,2][1,3][2,1][2,3][3,1][3,2]
   |      |     |     |     |     |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

每次递归的调用，就是在决策树上“向下走一步”；
每次回溯，就是在“退回上一个节点”。

---

三、回溯三要素

1. 路径（path）：当前已经做出的选择。
2. 选择列表（choices）：当前可以做的选择。
3. 结束条件（end）：到达决策树底层，无法再继续选择时。

---

四、回溯法通用模板

void backtrack(状态参数) {
    // 1. 判断结束条件
    if (满足结束条件) {
        记录结果;
        return;
    }

    // 2. 遍历所有选择
    for (选择 : 当前可选项集合) {
        // 做出选择
        做选择;

        // 进入下一层递归（向决策树更深处探索）
        backtrack(新的状态);

        // 撤销选择（回溯，返回上一个节点）
        撤销选择;
    }
}

---

五、典型示例：全排列

List<List<Integer>> res = new ArrayList<>();

public List<List<Integer>> permute(int[] nums) {
    backtrack(nums, new ArrayList<>());
    return res;
}

void backtrack(int[] nums, List<Integer> path) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }

    for (int num : nums) {
        if (path.contains(num)) continue;
        path.add(num);
        backtrack(nums, path);
        path.remove(path.size() - 1);
    }
}

解释：

• 每次递归表示进入决策树下一层；
• path.add() 是“走下去”；
• path.remove() 是“回退”；
• 整个递归树遍历完毕，即得到所有排列结果。

---

六、剪枝优化

剪枝（Pruning）是回溯算法提升效率的关键。
在进入下一层递归前，先判断是否有必要继续下探：

• 若当前路径已不可能得到更优解，则剪掉该分支。
• 可显著减少无效搜索，提高性能。

---

七、回溯的本质

一句话总结：

回溯 = 枚举所有可能解的 DFS + 剪枝优化。

它以“决策树”的形式遍历搜索空间，
通过“选择 → 递归 → 回退”三步循环，逐步构建完整解。

---