回溯算法：从迷宫探索到解题套路

哈喽，大家好呀，我是 Leo，今天我们来聊聊回溯算法,一个听起来很玄乎，其实就是”走不通就回头”的朴素思想。

你有没有过这样的经历？走进一个复杂的迷宫，选了一条路走下去，发现是死胡同，于是退回来，换另一条路再试。这不就是回溯吗？

回溯的本质就是在搜索树上做 DFS,从一条路往前走，能进则进，不能进则退回来换条路。听起来简单，但为什么很多人刷回溯题总是不得要领？

因为他们没有抓住回溯的”骨架”。接下来听我娓娓道来～

回溯三部曲：所有题目的通用骨架

不管题目怎么变，回溯的代码结构基本是固定的。掌握这个模板，你就掌握了 80% 的回溯题。

1
2
3
4
5
6
7
8
9
10
11
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择 : 本层集合) {
        处理节点;
        backtracking(路径, 选择列表); // 递归
        回溯，撤销处理结果;
    }
}

就这么几行代码，藏着三个关键点：

  1. 终止条件：什么时候算找到了一个解？
  2. 单层搜索逻辑：这一层我有哪些选择？
  3. 回溯撤销：退回来的时候，要把刚才的痕迹擦掉

这个模板就像一个框架，你只需要根据具体题目往里面填内容。问题是——填什么？

一眼识别：五大题型对号入座

回溯题目虽然多，但逃不出这五类：

类型 特点 代表题目 关键技巧
组合问题 选 k 个数，顺序无关 77.组合、39.组合总和 startIndex 控制起点
排列问题 全排列，顺序有关 46.全排列、47.全排列II used 数组标记已用
切割问题 把字符串切成几段 131.分割回文串、93.复原IP startIndex 即切割点
子集问题 找所有子集 78.子集、90.子集II 收集所有节点，不只是叶子
棋盘问题 N皇后、数独 51.N皇后、37.解数独 二维递归 + 合法性检查

怎么区分组合和排列？ 很简单：[1,2] 和 [2,1] 算不算同一个结果？算就是组合，不算就是排列。

组合问题：startIndex 是灵魂

组合问题最核心的技巧就是 startIndex——控制每次从哪里开始选，避免重复组合。

基础模板：77.组合

从 1 到 n 中选 k 个数的所有组合： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();

void backtracking(int n, int k, int startIndex) {
    if (path.size() == k) {
        result.add(new ArrayList<>(path));
        return;
    }
    // 剪枝优化：剩余元素不够 k 个时提前终止
    for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
        path.add(i);
        backtracking(n, k, i + 1); // 从 i+1 开始，不会重复选
        path.removeLast(); // 回溯
    }
}

为什么需要 startIndex？ 如果每次都从 0 开始，[1,2] 和 [2,1] 都会出现。有了 startIndex，保证选出的数是递增的，自然去重。

剪枝公式 i <= n - (k - path.size()) + 1 是什么意思？还差 3 个数凑够 k 个，但只剩 2 个数可选了，那还遍历个啥？直接跳过。

可重复选取：39.组合总和

这题的坑点在于：同一个数可以无限次使用。怎么改？递归时传 i 而不是 i + 1： 

1
backtracking(candidates, target, i, sum); // 注意是 i，不是 i+1

这样就允许重复选当前元素了。

排列问题：used 数组来帮忙

排列和组合最大的区别：组合用 startIndex，排列用 used 数组。

为什么？因为排列每次都要从 0 开始遍历（顺序有关），但要知道哪些元素已经被用过了。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] used;

void backtracking(int[] nums) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) { // 每次从 0 开始
        if (used[i]) continue; // 已使用的跳过
        path.add(nums[i]);
        used[i] = true;
        backtracking(nums);
        used[i] = false; // 回溯
        path.removeLast();
    }
}

去重的艺术：树层 vs 树枝

当数组中有重复元素时，去重是最大的坑。

关键区分：

  • 树层去重：同一层不能有相同元素（用过的被回溯了，used[i-1] == false）
  • 树枝去重：同一分支可以有相同元素（还在当前路径上，used[i-1] == true）
1
2
3
4
// 树层去重：同一层遇到相同元素跳过
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
    continue;
}

必须先排序！ 不排序的话，相同元素不相邻，去重逻辑就失效了。

子集问题：收集所有节点

组合和排列只在叶子节点收集结果，子集问题不同——每个节点都是一个合法答案。

1
2
3
4
5
6
7
8
void backtracking(int[] nums, int startIndex) {
    result.add(new ArrayList<>(path)); // 进来就收集，不只是叶子
    for (int i = startIndex; i < nums.length; i++) {
        path.add(nums[i]);
        backtracking(nums, i + 1);
        path.removeLast();
    }
}

就这么简单，把收集结果的操作从终止条件里挪到函数开头。

棋盘问题：N皇后的优雅

N皇后是回溯的经典应用，核心是逐行放置 + 合法性检查：

1
2
3
4
5
6
7
8
9
10
11
12
13
void backtracking(int n, int row, char[][] board) {
    if (row == n) {
        result.add(arrayToList(board));
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, n, board)) {
            board[row][col] = 'Q';
            backtracking(n, row + 1, board); // 递归下一行
            board[row][col] = '.'; // 回溯
        }
    }
}

为什么逐行放置？ 每行只放一个皇后，天然避免了同行冲突，只需要检查列和对角线。

避坑指南：三个常见错误

1. 忘记回溯撤销

1
2
3
path.add(num);
backtracking(...);
// 忘了 path.removeLast()！

这会导致路径污染，后面的结果里混入了前面的元素。

2. 去重没排序

树层去重的前提是相同元素相邻。不排序就去重，等于白搭。

3. startIndex 和 used 搞混

  • 组合/子集/切割：用 startIndex
  • 排列：用 used 数组

用错了要么漏解，要么重复。

总结：一张表搞定所有场景

问题类型 startIndex used数组 收集时机 能否重复选
组合 ✓ ✗ 叶子节点 看题目
排列 ✗ ✓ 叶子节点 ✗
子集 ✓ ✗ 所有节点 ✗
切割 ✓ ✗ 叶子节点 ✗
棋盘 ✗ ✗ 叶子节点 ✗

碎碎念

回溯这东西，说难不难，说简单也不简单。不难在于模板固定，不简单在于细节太多——剪枝怎么写？去重怎么搞？什么时候用 startIndex，什么时候用 used？

我的建议是：先背模板，再刷题验证。把模板敲熟了，遇到新题往里面套，慢慢就有感觉了。

记住一句话：回溯不是魔法，就是有纪律的穷举。穷举不可怕，可怕的是没有剪枝的穷举——那是真·暴力。

刷题愉快，我们下期见！

相关题目推荐：

  • 入门：77.组合、46.全排列、78.子集
  • 进阶：39.组合总和、131.分割回文串、51.N皇后
  • 挑战：37.解数独、301.删除无效括号