专题 08递归与回溯：枚举所有可能

8.1回溯 = 递归 + 撤销选择

回溯解决的是「枚举所有可能」的问题。比如「从 1,2,3 里选 2 个数有哪些组合」「把 abc 全排列」。 暴力枚举的本质，是在一棵决策树上做深度优先搜索（DFS）：每个节点代表「当前已经做了哪些选择」，往下走一步就是「再做一个选择」。

关键就在「撤销」二字。DFS 走到一个分支、收集完结果后，要退回上一层，把刚才的选择取消，才能去试另一条分支。 就像走迷宫：走进死胡同，得沿原路退回来，才能走另一条岔路。这个「退回来」的动作，就是回溯里那句 path.remove(...)。

从 [1,2,3] 选 2 个（组合）的决策树：

            path=[]
        /      |      \
    选1        选2      选3
   path=[1]  path=[2]  path=[3]
    /  \       |          
  选2  选3     选3         (选3后再选>3的，无路)
[1,2][1,3]   [2,3]
    ↑ 三个叶子就是答案：[1,2][1,3][2,3]

注意：选完 [1,2] 后，必须「撤销 2」回到 [1]，
再「撤销 1」回到 []，才能去试选 2 那条分支。

把「做选择 → 递归 → 撤销选择」三步套在 DFS 上，这就是回溯的全部秘密。 后面所有题，骨架都一样，变的只是「什么时候算一个答案」「怎么避免重复」。

把决策树和代码逐行对上

拿「从 [1,2,3] 选 2 个」再走一遍，把树的每一步对应到回溯代码的执行流，你就能彻底看清「撤销」发生在哪：

回溯代码（组合 k=2）的执行轨迹：

backtrack(path=[], start=1)
  for i=1: path=[1]
    backtrack(path=[1], start=2)
      for i=2: path=[1,2] → 长度==k → 收 [1,2]；回到本层
        path.remove → path=[1]          ← 【撤销】2，退回选 2 之前
      for i=3: path=[1,3] → 收 [1,3]
        path.remove → path=[1]          ← 【撤销】3
    （i 循环结束）path.remove → path=[]  ← 【撤销】1，退回起点
  for i=2: path=[2]
    backtrack(path=[2], start=3)
      for i=3: path=[2,3] → 收 [2,3]
        path.remove → path=[2]
    path.remove → path=[]
  for i=3: path=[3]
    backtrack(path=[3], start=4) → i 从 4 起，啥也不选，直接返回
    path.remove → path=[]
收集到 [1,2][1,3][2,3] ✓

注意那三处 path.remove：每一层递归返回前，都必须把刚加进去的元素撤销， 否则上层循环再 path.add 时，path 里还残留着下层的选择，答案就串味了。 「撤销」和「做选择」严格对称，是回溯能正确枚举的核心纪律。

8.2回溯通用模板：决策树

把上面的思想落成代码，所有回溯题都是这四件套：

void backtrack(路径 path, 选择列表, 结果集 res) {
    if (满足结束条件) {        // 比如 path 长度够了
        res.add(拷贝(path));   // 注意：加的是拷贝，不是引用
        return;
    }
    for (每个可选选择) {
        path.add(选择);        // ① 做选择
        backtrack(path, ...);  // ② 递归进下一层
        path.remove(最后);     // ③ 撤销选择（回溯的灵魂）
    }
}

逐行注意点：

• 结束条件：告诉递归「什么时候这个 path 算一个完整答案」。组合是 path 长度等于 k，子集是每个节点都收，全排列是 path 长度等于 n。
• 加拷贝：res.add(new ArrayList<>(path))。如果不拷贝，后面撤销 path 时，res 里存的同一个对象也被改空，最后全变空列表。这是新手第一坑。
• 撤销必须对称：加了什么就移除什么，顺序无所谓（移除最后一个即可），但绝不能漏。
• 选择列表怎么缩：用 start 参数保证「不回头选」，用 used 数组标记「已用过」，避免重复——这两招后面分别讲。

8.3组合（中等，力扣 77）

中等 核心：start 参数防重复

题意：从 1 到 n 里选 k 个数，返回所有组合（不考虑顺序，[1,2] 和 [2,1] 算同一个，只留 [1,2]）。 例：n=4, k=2 → [1,2][1,3][1,4][2,3][2,4][3,4]。

思路推导

用决策树想：第一个数可以选 1~n，选了之后第二个数只能从「比它大的」里选，这样自然不会重复（不会出现 [2,1]）。 怎么在代码里表达「只能选更大的」？加一个 start 参数：本层只从 start 到 n 枚举，递归时传 start+1。 因为下一层从 i+1 开始，永远不会回头选更小的，所以 [1,2] 和 [2,1] 不会被都生成。

n=4,k=2 的决策树（start 控制不回头）：
        []
   1     2     3     4
  2 3 4  3 4   4      (4后再无更大)
 [12][13][14][23][24][34]  ✓ 六个，无重复

参考代码

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        backtrack(n, k, 1, path, res);   // start 从 1 开始
        return res;
    }

    private void backtrack(int n, int k, int start, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == k) {                    // 选满 k 个，收答案
            res.add(new ArrayList<>(path));        // 拷贝！
            return;
        }
        for (int i = start; i <= n; i++) {          // 只从 start 往后，防重复
            path.add(i);                           // 做选择
            backtrack(n, k, i + 1, path, res);     // 下一层从 i+1 起
            path.remove(path.size() - 1);          // 撤销
        }
    }
}

复杂度

时间 O(C(n,k) × k)：共 C(n,k) 个组合，每个拷贝 path 花 O(k)。空间 O(k) 递归栈 + 结果集。 为什么 i+1 而非 start？传 start 会重复选同一位置导致无限递归；传 i+1 才保证「不回头」。

8.4子集（中等，力扣 78）

中等 核心：每个节点都收集

题意：给定数组（无重复元素），返回所有子集。例：[1,2,3] → 8 个：[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]。

思路推导

子集和组合的区别在哪？组合只要「长度恰好 k 的」；子集要所有长度的，包括空集。 所以决策树里每一个节点都是一个合法答案，不能只在叶子收，要「每往下走一步就收一次」。

仍用 start 防重复（同组合一样，元素不重复使用）。区别仅在结束条件：子集没有「必须选满」的硬要求， 递归自然会在 for 走完时停下；而「收集答案」放在递归函数最开头，每进入一层就先把当前 path 收进去。

[1,2,3] 子集决策树（每个节点都收）：
        []            ← 收 []
     /  |  \
   1    2    3       ← 收 [1][2][3]
  / \   |
 2   3  3            ← 收 [1,2][1,3][2,3]
 |
3                ← 收 [1,2,3]
共 8 个 = 2^3 ✓

参考代码

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

    private 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);   // 不回头
            path.remove(path.size() - 1);        // 撤销
        }
        // 没有「长度等于 k」的硬性结束，for 走完自然回退
    }
}

复杂度

时间 O(2ⁿ × n)：共 2ⁿ 个子集，每个拷贝 O(n)。空间 O(n) 递归栈。 为什么子集是「每个节点收集」而组合是「叶子收集」？因为子集允许任意长度，路径本身就是答案； 组合只认长度恰到好处的那条，所以只在 path.size()==k 时收。两题骨架几乎一模一样，差的就是这一句放哪。

8.5全排列（中等，力扣 46）

中等 核心：used 数组防重用

题意：给定数组（无重复），返回所有全排列（顺序不同算不同）。例：[1,2,3] → 6 个排列。

思路推导

排列和组合/子集最大的不同：每个数必须用且仅用一次，但顺序任意。 组合用 start 保证「不回头」来避免重复；但排列里 [1,2,3] 和 [2,1,3] 都是合法答案，不能「不回头」。 那怎么避免「同一个数用两次」？用 used 布尔数组标记哪些数已被选入当前 path，for 循环里跳过已用的。

[1,2,3] 全排列（used 挡住重复用）：
第一层可选 1/2/3（都未用）
选1 → used[1]=true → 第二层可选 2/3
  选2 → 第三层只能选 3 → [1,2,3]
  选3 → 第三层只能选 2 → [1,3,2]
选2 → ... → [2,1,3][2,3,1]
选3 → ... → [3,1,2][3,2,1]
共 6 = 3! ✓

参考代码

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[nums.length];   // 标记用过没
        backtrack(nums, used, path, res);
        return res;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {            // 选满 n 个，一个排列完成
            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;                          // 撤销标记（对称的！）
        }
    }
}

复杂度

时间 O(n! × n)：共 n! 个排列，每个拷贝 O(n)。空间 O(n) 递归栈 + used 数组。 为什么组合用 start、排列用 used？组合/子集要「不回头」去重，排列要「每个都能放任意位置但不能重复用」—— 本质区别是要不要保留顺序自由。背住这个对照，三题就不会混。

8.6N 皇后（困难，力扣 51）

困难 核心：回溯模板的完整形态

题意：在 n×n 棋盘上放 n 个皇后，使任意两个不互相攻击（不在同一行、同一列、同一对角线）。返回所有摆法。 例：n=4 有 2 种解。

思路推导

N 皇后是回溯模板的「完整形态」——组合/子集/排列的技巧它全用上：

• 一行一行放皇后（每行必放一个，天然保证不同行）；
• row 参数相当于「当前层」，递归到 row==n 说明 n 行都放完，收一个解；
• 每一层 for 循环枚举这一行的每一列，用 isValid 检查「同列 / 左上方对角线 / 右上方对角线」有没有冲突；
• 放的格子标记 'Q'，递归返回后改回 '.'——这就是「撤销选择」。

对角线判断的直觉：对于已放的行 r'（r' < row），若它放在列 c'，那么要挡住当前 (row, col)，需满足 col == c'（同列），或 row - r' == col - c'（左上↘方向，行差=列差），或 row - r' == c' - col（右上↙方向）。 把后两个合并成 abs(row - r') == abs(col - c') 即「同一对角线」。

参考代码（完整可提交）

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++)                 // 棋盘初始化为 '.'
            for (int j = 0; j < n; j++) board[i][j] = '.';
        backtrack(board, 0, n, res);               // 从第 0 行开始
        return res;
    }

    // 在第 row 行尝试放皇后
    private void backtrack(char[][] board, int row, int n, List<List<String>> res) {
        if (row == n) {                            // 0..n-1 都放完 → 一个解
            res.add(construct(board));
            return;
        }
        for (int col = 0; col < n; col++) {        // 枚举这一行的每一列
            if (isValid(board, row, col, n)) {
                board[row][col] = 'Q';            // 做选择
                backtrack(board, row + 1, n, res); // 下一行
                board[row][col] = '.';            // 撤销选择
            }
        }
    }

    // 检查 (row, col) 能不能放：同列 / 左上方 / 右上方 有无皇后
    private boolean isValid(char[][] board, int row, int col, int n) {
        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;
    }

    // 把 char 矩阵转成 List<String> 方便输出
    private List<String> construct(char[][] board) {
        List<String> list = new ArrayList<>();
        for (char[] r : board) list.add(new String(r));
        return list;
    }
}

复杂度

时间最坏 O(n!)（每行排除已占列，类似排列），实际因对角线剪枝远小于此。空间 O(n²) 棋盘 + O(n) 递归栈。 为什么只查「上方」的冲突？因为下方还没放皇后，只需保证和已放的行不冲突即可——这正体现回溯「逐步决策」的特点。

8.7剪枝：回溯的效率生命线

回溯慢的根因是「枚举了太多注定失败的分支」。剪枝（Pruning）就是在还没走到死胡同之前，提前判断「这条路不可能出答案」，直接不进去，把整棵子树砍掉。

组合剪枝公式的直观推导

回到组合（8.3）：n=4, k=2，已选 path=[1]，接下来 for 从 i=2 到 4。 但注意：还需要再选 k − path.size() = 1 个数。从位置 i 往后（含 i）还剩多少个数可挑？ 是 n − i + 1 个。要让「剩下的数」够选，必须满足：

剩下的可选数  ≥  还需要选的个数
n − i + 1     ≥  k − path.size()
移项得：i  ≤  n − (k − path.size()) + 1

这就是剪枝上界。例：n=4, k=2，path=[1]（已选 1 个），还需 1 个： i ≤ 4 − (2−1) + 1 = 4，所以 i 到 4 都行（[1,4] 合法）。 但若 path=[]、k=3、n=4：i ≤ 4 − (3−0) + 1 = 2，第一层只枚举到 2—— 因为选了 3 之后只剩 [4] 一个数，凑不够 3 个，整条分支砍掉，省掉大量递归。

把 for 循环的上界从 i <= n 改成 i <= n - (k - path.size()) + 1：

// 组合剪枝版（仅改 for 上界）
for (int i = start; i <= n - (k - path.size()) + 1; i++) {
    path.add(i);
    backtrack(n, k, i + 1, path, res);
    path.remove(path.size() - 1);
}

其他常见剪枝

• 子集 II 同层去重：if (i > start && nums[i] == nums[i-1]) continue; 跳过同层相同值，避免重复子集；
• 求和类（如组合总和）：若要求和等于 target，当前和已 > target 直接 return（前提是数组非负）；
• N 皇后：isValid 本身就是在「放之前」剪掉冲突列，是最直接的剪枝。

一个具体例子：求和剪枝（组合总和类）

假设题目变成「从 [2,3,6,7] 里选数（可重复），凑出和为 7 的所有组合」。递归到某一层 path=[2,2]、当前和 = 4， 接下来要选的数若再取 6，和变成 10 已经超过 7——这条分支整棵子树都不可能等于 7，直接 return 剪掉， 不用再往下深搜。代码骨架：

void backtrack(int[] nums, int target, int start, int sum, List<Integer> path, List<List<Integer>> res) {
    if (sum == target) { res.add(new ArrayList<>(path)); return; } // 凑齐，收
    if (sum > target) return;                                      // 超了，剪枝（数组非负才成立）
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, target, i, sum + nums[i], path, res); // 可重复就传 i 不传 i+1
        path.remove(path.size() - 1);
    }
}

这里 if (sum > target) return; 就是最朴素的剪枝：它把「和已超目标」的所有后续选择一次性砍光。 对比「不剪枝、硬搜到选满再判断」，在数组稍大时差距是数量级的——这也是为什么剪枝叫「回溯的效率生命线」。

8.8自测题