回溯：系统性枚举所有可能

这一课你将能做到

1. 说出回溯三要素（选择、路径、结束条件）和标准代码骨架
2. 用 used 数组写全排列，用「选 / 不选」写子集
3. 用行列、对角线约束完成 N 皇后，并理解剪枝为什么不丢解

为什么要学

有些问题没有捷径，就是要把所有可能的方案试一遍：排列有多少种、怎么排班、棋盘怎么放、括号怎么组合。回溯就是有纪律的穷举——沿着一条路走到底，发现走不通（或已得到一个完整方案）就退回上一步，换一个选择继续。它的优雅之处在于：不用你手工管理每一种方案，只要写清楚「当前有哪些选择」，框架会自动遍历整棵决策树。

回溯在实际开发中用得少，但面试出现率不低，而且是理解深度优先搜索（DFS）、剪枝、约束满足问题的入口。更重要的是它能治好一种焦虑：面对「全部方案」类题目不再发怵，因为你有一个万能骨架。

先建立图像

把求解过程画成一棵决策树：

        根
      / | \
    选1 选2 选3        ← 每层代表「这一步的选择」
   / \   ...
 选2  选3              ← 沿一条路径走到底 = 一个完整方案
  |
 选3 → [1,2,3] 记录，然后回退换选择

万能骨架：

void backtrack(路径, 选择集):
    if 满足结束条件:
        收集一份路径的副本
        return
    for 选择 in 当前可选项:
        做选择（更新路径/标记）
        backtrack(...)
        撤销选择（恢复现场）

关键纪律两条：收集答案时存的是副本（路径之后还会被改动）；做选择和撤销选择必须严格对称。

跟着做

步骤 1：LeetCode 46「全排列」（中等）

给定不含重复数字的数组，返回所有全排列。

用 used[] 标记某数字是否已在当前路径中：每层从所有未使用的数字里选一个。

import java.util.ArrayList;
import java.util.List;

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

    private void backtrack(int[] nums, boolean[] used,
                           List<Integer> path, 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;
            }
            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, used, path, result);
            path.remove(path.size() - 1); // 撤销，顺序与加入时相反
            used[i] = false;
        }
    }
}

逐点讲：时间 O(n · n!)（共 n! 个排列，每个拷贝 O(n)），空间 O(n)（递归深度 + path，不计结果）。若数组含重复值（LeetCode 47），先排序，遇到 i>0 && nums[i]==nums[i-1] && !used[i-1] 时跳过即可。

步骤 2：LeetCode 78「子集」（中等）

返回数组所有子集（幂集）。

子集没有「选满」的概念——回溯树的每个节点都是一个答案，进入函数先收集；然后只从 start 位置往后选，避免出现重复组合。

import java.util.ArrayList;
import java.util.List;

class Solution {
    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); // 只能往后选
            path.remove(path.size() - 1);
        }
    }
}

逐点讲：start 取代了 used——组合问题里元素先后不算区别，强制下标递增即可天然去重。时间 O(n · 2ⁿ)，空间 O(n)。

步骤 3：LeetCode 51「N 皇后」（困难）

在 n×n 棋盘放 n 个皇后，使任意两皇后不同行、不同列、不在同一斜线，返回所有摆法。

按行放置（每行恰一个皇后，行冲突自动消除）。用三个布尔数组记录占用：列、主对角线（行列之差恒定，加 n-1 偏移）、副对角线（行列之和恒定）。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        boolean[] cols = new boolean[n];
        boolean[] diag1 = new boolean[2 * n - 1]; // r - c + n - 1
        boolean[] diag2 = new boolean[2 * n - 1]; // r + c
        int[] placed = new int[n]; // 每行皇后所在列
        backtrack(0, n, placed, cols, diag1, diag2, result);
        return result;
    }

    private void backtrack(int row, int n, int[] placed,
                           boolean[] cols, boolean[] diag1, boolean[] diag2,
                           List<List<String>> result) {
        if (row == n) {
            result.add(buildBoard(placed, n));
            return;
        }
        for (int col = 0; col < n; col++) {
            int d1 = row - col + n - 1;
            int d2 = row + col;
            if (cols[col] || diag1[d1] || diag2[d2]) {
                continue; // 剪枝：这个位置必冲突，不必深入
            }
            placed[row] = col;
            cols[col] = diag1[d1] = diag2[d2] = true;
            backtrack(row + 1, n, placed, cols, diag1, diag2, result);
            cols[col] = diag1[d1] = diag2[d2] = false;
        }
    }

    private List<String> buildBoard(int[] placed, int n) {
        List<String> board = new ArrayList<>();
        for (int col : placed) {
            char[] line = new char[n];
            java.util.Arrays.fill(line, '.');
            line[col] = 'Q';
            board.add(new String(line));
        }
        return board;
    }
}

逐点讲：剪枝只剪掉「当前约束下必然冲突」的分支，合法方案一条不少。时间最坏 O(n!)，空间 O(n)（不计结果）。

讲清楚要点

1. 排列、子集（组合）的差别就在去重方式：排列用 used（顺序敏感）；组合用 start（顺序无关，下标只往后走）。
2. 答案收集位置决定语义：叶节点收集 = 等长方案（排列、N 皇后）；每个节点收集 = 所有前缀也算方案（子集）。
3. 剪枝的正确姿势是剪「必然不合法」而不是「看起来不优」，后者可能误杀答案。
4. 对称撤销是回溯的命门：加了什么标记就撤什么标记，多撤少撤都会让后续分支错乱。
5. 回溯 = DFS 在决策树上的应用，与图的 DFS 同源，区别只是「邻接节点」由当前可选项动态生成。

你可能会懵的地方

• 回溯和 DFS 到底是不是一回事？ 实现形式相同，视角不同：图的 DFS 遍历已存在的节点关系；回溯遍历一棵「虚拟的决策树」，子节点是现场构造的选择。可以说回溯是 DFS 的特化用法。

• 为什么必须 new ArrayList<>(path)，直接 add(path) 会怎样？ path 始终是同一个对象，后续撤销会改变它；直接 add 进去，结果列表里会全是同一个、最终为空的列表。副本才能定格那一刻。

• 子集用位运算枚举可以吗？ 可以，0～2ⁿ-1 每个比特位表示选不选，是非递归的幂集写法。回溯更通用（能处理更复杂的选择与剪枝），建议作为主武器。

• N 皇后对角线的下标怎么推导？ 同一条主斜线上 r-c 相同（范围 -(n-1)～n-1，加 n-1 平移成下标）；同一条副斜线上 r+c 相同（0～2n-2）。画三个格子验证一次即可记住。

• 回溯超时怎么办？ 先确认剪枝是否到位（开头排除、排序后相邻去重）；再想是否存在更优范式（记忆化 → 动态规划）。回溯本身是指数级，规模一大只能靠剪枝或换思想。

错法对照

错法	问题	正解
收集答案不拷贝	结果全被后续撤销污染	new ArrayList<>(path)
组合问题也用全量 for + used	生成大量重复组合	用 start 只往后选
撤销只删 path 不还原标记	后续分支可见性错误	选择与撤销严格对称
子集只在叶节点收集	丢掉所有短于 n 的子集	进函数先收集
剪枝条件凭感觉写	可能误删合法方案	只剪约束下确定非法的分支

卡点急救

1. 不知道结束条件写什么：问「一个完整方案长什么样」——排列是选满 n 个，N 皇后是放满 n 行；方案没有固定长度（子集）就不设结束、靠 for 自然终止。
2. 结果数量对但内容重复 / 缺失：排列查 used，组合查 start，含重复输入查排序 + 相邻跳过。
3. 撤销后状态混乱：把一次循环体里的「做选择」逐行列出，撤销段按相反顺序一一对应，不多不少。

面试常问

• 全排列如果有重复元素怎么办（LeetCode 47）？ 先排序，使相同值相邻；同一层递归中，若当前值与前一个相同且前一个未被使用（!used[i-1]），说明前一个同值分支已覆盖此情况，跳过即可。关键在「同层去重、不同层允许」。

• 括号生成（LeetCode 22）的思路？ 回溯中维护已用左括号数 left、右括号数 right：left < n 可加左括号；right < left 可加右括号（保证任何前缀右不超左）。长度达 2n 收集。这是「带计数约束的回溯」典型。

• 回溯能不能优化成动态规划？信号是什么？ 当递归中出现大量重复的子状态（相同参数被多次求解）时，加备忘录就成了记忆化搜索，再整理成自底向上的 DP。下一阶段的课程会系统讲，编辑距离就是从回溯加记忆化演化来的。

自测三问

1. 回溯三要素是什么？「做选择」和「撤销选择」为什么必须对称？
2. 排列用 used、子集用 start，背后的顺序敏感性差异是什么？
3. N 皇后如何用三个数组 O(1) 判断冲突？剪枝为什么不丢解？

小结一句话

回溯就是「走不通就退回、换一条再走」的系统化枚举：排列靠 used、组合靠 start、约束题靠剪枝，记得存副本、对称撤销。

延伸

• 巩固练习：LeetCode 39 组合总和、LeetCode 22 括号生成、LeetCode 47 全排列 II
• 在本站在线判题平台提交，试试 n=1、n=4 的 N 皇后，对照方案个数
• 下一课预告：图与 Trie——岛屿数量、克隆图、前缀树，把 DFS/BFS 用到节点关系网络上