回溯：剪枝与状态空间树

回溯的本质

回溯（Backtracking） 是一种通过系统地枚举所有可能候选解并撤销不合法选择的算法范式。

回溯 = 暴力枚举 + 剪枝
回溯 = DFS 遍历决策树

它本质上是一棵决策树（状态空间树） 的 DFS，在走不通时回头（撤销选择）。

回溯的通用模板

// 回溯通用模板
void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        result.add(路径的副本);  // 注意：必须是副本！
        return;
    }
    for (选择 in 选择列表) {
        if (不合法) continue;      // 剪枝
        做选择;                     // 修改状态
        backtrack(路径, 新选择列表);
        撤销选择;                   // 恢复状态（回溯）
    }
}

三类经典问题

1. 全排列（元素不重复）

// LeetCode 46
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(nums, used, new ArrayList<>(), res);
    return res;
}

void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path));  // 深拷贝！
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;       // 剪枝：已使用
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path, res);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

2. 子集（元素不重复）

// LeetCode 78
void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));  // 每个节点都是一个子集
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res);  // i+1：不重用当前元素
        path.remove(path.size() - 1);
    }
}

3. 组合总和（元素可复用）

// LeetCode 39
void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {
    if (target == 0) { res.add(new ArrayList<>(path)); return; }
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > target) break;  // 已排序，剪枝
        path.add(candidates[i]);
        backtrack(candidates, target - candidates[i], i, path, res);  // i：可重用
        path.remove(path.size() - 1);
    }
}

去重：有重复元素时的剪枝

// LeetCode 47 全排列II（含重复数字）
// 关键：排序后，相同元素只使用一次（同层去重）
void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        // 同层去重：nums[i] == nums[i-1] 且 nums[i-1] 未被使用（同层的上一个）
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path, res);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

去重的两种方式对比：

N 皇后——二维约束

// LeetCode 51
public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    int[] queens = new int[n];  // queens[i] = 第i行皇后的列号
    Arrays.fill(queens, -1);
    Set<Integer> cols = new HashSet<>(), diag1 = new HashSet<>(), diag2 = new HashSet<>();
    backtrack(queens, n, 0, cols, diag1, diag2, res);
    return res;
}

void backtrack(int[] queens, int n, int row,
               Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2,
               List<List<String>> res) {
    if (row == n) { res.add(buildBoard(queens, n)); return; }
    for (int col = 0; col < n; col++) {
        if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) continue;
        queens[row] = col;
        cols.add(col); diag1.add(row - col); diag2.add(row + col);
        backtrack(queens, n, row + 1, cols, diag1, diag2, res);
        queens[row] = -1;
        cols.remove(col); diag1.remove(row - col); diag2.remove(row + col);
    }
}

剪枝技巧总结

回溯 vs DFS

回溯本质是 DFS，但侧重点不同：

复杂度分析

速查：常见回溯题