回溯算法

为什么回溯算法很重要

回溯算法通过递增地构建解，并放弃那些无法导向有效解的局部解，从而系统地探索所有可能性：

• 组合问题：生成所有的排列或组合。
• 约束满足问题：数独、N 皇后问题、填字游戏。
• 路径搜索：迷宫求解、图遍历。
• 最优化问题：在众多可能性中寻找最优解。

实际影响：

• 使用回溯法解决 N 皇后问题：N=8 时仅需 2 秒。
• 暴力检查所有位置：N=8 时约需 4 小时。
• 速度提升 7200 倍。

核心概念

回溯模板

void backtrack(state, parameters) {
    if (isSolution(state)) {
        recordSolution(state);
        return;
    }

    for (choice in generateChoices(state)) {
        if (isValid(choice)) {
            makeChoice(choice);
            backtrack(state, parameters);
            undoChoice(choice);  // 回溯（撤销选择）
        }
    }
}

回溯 vs 递归

维度	回溯	递归
搜索空间	系统化探索所有可能	分而治之
剪枝	激进（提前终止）	通常不包含剪枝
用例	约束满足问题	问题拆解/子问题求解
状态管理	需要手动做出/撤销选择	通常不需要状态回滚

深入理解

全排列 (Permutations)

生成所有可能的排列方案：

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

private void backtrack(List<List<Integer>> result, List<Integer> current,
                      boolean[] used, int[] nums) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;

        current.add(nums[i]);
        used[i] = true;

        backtrack(result, current, used, nums);

        current.remove(current.size() - 1);  // 回溯
        used[i] = false;
    }
}

组合 (Combinations)

生成所有包含 k 个元素的组合：

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), 1, n, k);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> current,
                      int start, int n, int k) {
    if (current.size() == k) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = start; i <= n; i++) {
        current.add(i);
        backtrack(result, current, i + 1, n, k);  // 注意：是 i + 1 而不是 start
        current.remove(current.size() - 1);  // 回溯
    }
}

剪枝策略

在排列中去除重复项

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);  // 排序以便将重复项聚集在一起
    backtrack(result, new ArrayList<>(), new boolean[nums.length], nums);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> current,
                      boolean[] used, int[] nums) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;

        // 跳过重复：仅使用重复数字中的第一个出现项
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

        current.add(nums[i]);
        used[i] = true;

        backtrack(result, current, used, nums);

        current.remove(current.size() - 1);
        used[i] = false;
    }
}

常见陷阱

❌ 添加结果时未进行深拷贝

if (current.size() == k) {
    result.add(current);  // 错误：添加的是引用！
}

✅ 创建新副本

if (current.size() == k) {
    result.add(new ArrayList<>(current));  // 进行拷贝
}

❌ 忘记撤销选择

for (int i = 0; i < n; i++) {
    current.add(i);
    backtrack(current);
    // 忘记移除元素！
}

✅ 始终执行回溯

for (int i = 0; i < n; i++) {
    current.add(i);
    backtrack(current);
    current.remove(current.size() - 1);  // 撤销选择
}

实际应用

N 皇后问题

public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    char[][] board = new char[n][n];

    for (int i = 0; i < n; i++) {
        Arrays.fill(board[i], '.');
    }

    backtrack(result, board, 0);
    return result;
}

private void backtrack(List<List<String>> result, char[][] board, int row) {
    int n = board.length;

    if (row == n) {
        result.add(constructBoard(board));
        return;
    }

    for (int col = 0; col < n; col++) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';
            backtrack(result, board, row + 1);
            board[row][col] = '.';  // 回溯
        }
    }
}

private boolean isValid(char[][] board, int row, int col) {
    int n = board.length;

    // 检查同一列
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }

    // 检查左上对角线
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }

    // 检查右上对角线
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }

    return true;
}

面试题

Q1：子集 (中等)

题目：生成集合的所有子集。

方法：对每个元素决定包含或不包含。

复杂度：O(2ⁿ) 时间。

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), nums, 0);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> current,
                      int[] nums, int start) {
    result.add(new ArrayList<>(current));

    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);
        backtrack(result, current, nums, i + 1);
        current.remove(current.size() - 1);
    }
}

Q2：组合总和 (中等)

题目：找出所有和为目标值的组合（允许元素重复使用）。

方法：回溯结合目标值递减。

复杂度：O(N^(T/M+1)) 时间（N 为候选数，T 为目标值，M 为最小候选值）。

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(candidates);  // 排序以支持提前终止（剪枝）
    backtrack(result, new ArrayList<>(), candidates, target, 0);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> current,
                      int[] nums, int remain, int start) {
    if (remain == 0) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = start; i < nums.length; i++) {
        if (nums[i] > remain) break;  // 剪枝：提前停止

        current.add(nums[i]);
        backtrack(result, current, nums, remain - nums[i], i);  // 使用 i 而非 i+1 允许重复使用
        current.remove(current.size() - 1);
    }
}

延伸阅读

• 动态规划 (DP)：用于解决最优化子问题，通常比纯回溯更高效。
• 递归：回溯算法的基础。
• 深度优先搜索 (DFS)：图探索过程本质上使用了回溯。
• LeetCode：回溯标签题目