S03-J04 · 回溯与搜索：把"枚举"写成树

适用读者：写得出全排列，但一遇到"去重""剪枝"就乱的人。
前置：S03-B06（树）。
实测环境：Python 3.12.3（N 皇后搜索节点统计）；实测日期 2026-11-05。
覆盖旧文：17、22、37、39、40、46、47、51、52、77、78、79、90、93（14 张卡，2,416 点）。
覆盖扩展：E-S03-018（去重：排序 + 同层跳过）。
补写：#51 N 皇后（空壳，E-S03-117）、#79 单词搜索（空壳，E-S03-118）。
上一篇：S03-J03 · 链表操作：指针的四种基本动作
下一篇：S03-J05 · 动态规划。

1. 一句话结论

回溯 = 在决策树上做 DFS + 撤销现场。三个动作固定不变：选择 → 递归 → 撤销。

void dfs(状态) {
    if (满足结束条件) { 收集答案; return; }
    for (候选 : 当前可选项) {
        if (!合法(候选)) continue;   // 剪枝
        做选择(候选);
        dfs(新状态);
        撤销选择(候选);              // 关键，别漏
    }
}

三个最容易错的地方：

错法	后果
忘撤销	后面所有分支都带着脏状态
撤销顺序错（多值状态）	部分恢复，状态错乱
去重放在错误层级	漏解或重复解

2. 实测：剪枝到底省多少（N 皇后）

N 皇后：每行放一个皇后，列与两条对角线不能冲突。暴力是 nⁿ 种放法（n=8 → 1,677 万）。

n	解数	实际搜索节点数	相对暴力
8	92	2,057	1,677 万 → 2 千（省 8,000×）
10	724	35,539	10¹⁰ → 3.5 万
12	14,200	856,189	12¹² ≈ 8.9×10¹²

读法：每层只试"不与上面冲突"的位置，冲突判断本身就是最有效的剪枝。这就是"合法即剪枝"——不需要额外技巧。

3. 去重：排序 + 同层跳过（E-S03-018）

问题：有重复元素时，[1,1,2] 的全排列会生成重复结果。

解法（唯一推荐）：

Arrays.sort(nums);                      // ① 先排序，让相同值相邻
boolean[] used = new boolean[n];
void dfs(List<Integer> path) {
    if (path.size() == n) { res.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        // ② 同层去重：相同值只用第一个
        if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
        used[i] = true; path.add(nums[i]);
        dfs(path);
        path.remove(path.size()-1); used[i] = false;
    }
}

!used[i-1] 的含义：nums[i-1] 已经撤销（回到了同层）→ 说明"用值 v 开头的分支已经走过一次"，跳过。

场景	去重条件
全排列 II（#47）	`nums[i]==nums[i-1] && !used[i-1]`
组合总和 II（#40）	`i > start && nums[i]==nums[i-1]`
子集 II（#90）	同 #40

关键区别：排列要 used，组合不要（组合靠 start 保证不回头）。

4. 代表题精讲

4.1 #51 N 皇后（补写 `E-S03-117`）

int n; boolean[] col, d1, d2;      // d1: r-c+n, d2: r+c
List<List<String>> res = new ArrayList<>();
void dfs(int r, char[][] board) {
    if (r == n) { res.add(render(board)); return; }
    for (int c = 0; c < n; c++) {
        if (col[c] || d1[r-c+n] || d2[r+c]) continue;   // 剪枝
        col[c] = d1[r-c+n] = d2[r+c] = true;
        board[r][c] = 'Q';
        dfs(r+1, board);
        board[r][c] = '.';
        col[c] = d1[r-c+n] = d2[r+c] = false;           // 撤销
    }
}

要点：三条标记数组（列/主对角/副对角）代替"检查整个棋盘"，把单次合法性判断降到 O(1)。

4.2 #79 单词搜索（补写 `E-S03-118`）

boolean dfs(char[][] b, int i, int j, String w, int k) {
    if (k == w.length()) return true;
    if (i<0||i>=b.length||j<0||j>=b[0].length||b[i][j]!=w.charAt(k)) return false;
    char t = b[i][j]; b[i][j] = '#';        // 标记已访问
    boolean ok = dfs(b,i+1,j,w,k+1)||dfs(b,i-1,j,w,k+1)
              || dfs(b,i,j+1,w,k+1)||dfs(b,i,j-1,w,k+1);
    b[i][j] = t;                             // 撤销
    return ok;
}

边界：起点要遍历整个网格；b[i][j]='#' 是"路径内不能复用同一格"的最省做法。

4.3 #22 括号生成

剪枝条件（两条就够）：左括号数 < n 可放左；右括号数 < 左括号数 可放右。

4.4 #37 解数独

优化顺序：先填"候选最少"的格子（MRV 启发式）。用三个位掩码（行/列/宫）记录已用数字，单格候选 = ~(row|col|box) & 0x1FF。

4.5 #93 复原 IP

边界三件套：每段 1–3 位、数值 ≤255、不能有前导 0（"01" 非法）；4 段用完且指针到末尾才算解。

5. 14 题模式对照

题	去重方式	剪枝
17	无	无（笛卡尔积）
22	无	左 < n、右 < 左
37	无	位掩码候选
39	`start` 允许重复	剩余和不足
40	`i>start && 相等跳过`	剩余和不足
46	`used`	无
47	`used` + 同层跳过	无
51/52	无	列/双对角（补写 51）
77	`start`	剩余不够
78	无	无
79	网格标记	边界与字符（补写）
90	同层跳过	无
93	前导 0	段数/长度

6. 五个误区

误区	真相
"回溯就是递归"	关键在撤销；只递归不撤销会污染后续分支
"去重靠 `Set` 去结果"	能过但慢；排序 + 同层跳过是标准解
"剪枝要先算最优"	合法性判断本身就是最强剪枝（N 皇后实测 8,000 倍）
"组合和排列去重一样"	组合靠 `start`，排列靠 `used`
"递归深度不用担心"	棋盘/网格题深度可控，但"枚举子集"n=20 时 2²⁰ 就爆

7. 自检

回溯的三段式是什么？漏掉"撤销"会怎样？
!used[i-1] 那行去重条件的含义？
组合去重为什么不需要 used？
N 皇后 n=8 的实际搜索节点数是多少？与暴力差多少倍？
#79 为什么用"改字符为 #"而不是额外 visited 数组？

8. 下一篇

S03-J05 · 动态规划：状态定义与转移的推导法

回溯是"枚举所有可能"，DP 是"只算一次、复用结果"。下一篇用实测说明差距：爬楼梯 n=35 时纯递归 2,488.7 ms，记忆化 0.052 ms，迭代 0.011 ms。

本篇属于系列《S03 · 数据结构与算法》。旧文来源：14 张题解卡；补写 #51（E-117）、#79（E-118）。N 皇后节点数（2,057 / 35,539 / 856,189）为 2026-11-05 实测。