跳到主要内容

回溯与搜索

问题​

什么是回溯算法？常见的回溯题型有哪些？

答案​

回溯模板​

通用回溯框架
void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        result.add(路径);
        return;
    }
    for (选择 : 选择列表) {
        做选择;
        backtrack(路径, 选择列表);
        撤销选择;  // 回溯
    }
}

全排列​

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

private void backtrack(int[] nums, List<Integer> path, 
                       boolean[] used, List<List<Integer>> result) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));  // 注意拷贝
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;  // 跳过已使用的
        path.add(nums[i]);
        used[i] = true;
        backtrack(nums, path, used, result);
        path.remove(path.size() - 1);  // 撤销
        used[i] = false;               // 撤销
    }
}

子集​

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

private void backtrack(int[] nums, int start, List<Integer> path,
                       List<List<Integer>> result) {
    result.add(new ArrayList<>(path));  // 每个路径都是一个子集
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, result);  // 从 i+1 开始避免重复
        path.remove(path.size() - 1);
    }
}

岛屿数量（DFS）​

岛屿数量
public int numIslands(char[][] grid) {
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);  // 将整个岛标记为已访问
                count++;
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length 
        || grid[i][j] != '1') return;
    grid[i][j] = '0';  // 标记已访问
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

常见面试问题​

Q1: 回溯和 DFS 的关系？​

答案：

回溯是 DFS 的一种应用。DFS 是遍历策略（深度优先搜索），回溯是在 DFS 的基础上加上"撤销选择"，用于穷举所有可能的解。

Q2: 如何剪枝优化？​

答案：

在回溯过程中，尽早判断当前路径不可能通向有效解，提前终止。例如：

  • 组合总和：如果当前和已经超过目标，直接 return
  • N 皇后：检查同列、对角线冲突

相关链接​