回溯¶

一句话：回溯就是 DFS 加上一句"撤销现场"——穷举所有可能解的通用框架是「做选择 → 递归进入下一层 → 撤销选择」，三步缺一不可。写不出撤销那一步，是这类题最常见的翻车原因。

固定框架：选择、递归、撤销¶

46-全排列、78-子集、39-组合总和、22-括号生成、51-N皇后 看起来是完全不同的问题，但代码骨架一模一样：

void backtrack(路径, 选择列表):
    if 满足结束条件:
        记录路径的拷贝; return
    for 选择 in 选择列表:
        做选择(路径.add(选择))
        backtrack(路径, 新的选择列表)
        撤销选择(路径.removeLast())

"记录路径的拷贝"和"撤销选择"是最容易漏掉的两步：路径通常用一个可变的 List 复用，如果直接把这个引用存进结果集，后续的撤销/添加会连带修改已经"记录"的答案——必须拷贝一份新的 List。撤销选择如果漏写，路径会一直增长，后续分支会带着不属于自己的选择继续递归。

怎么判断该不该剪枝¶

39-组合总和、40-组合总和II、90-子集II 都涉及去重/剪枝：同一层的选择列表里，如果排序后相邻两个值相等，且前一个值在本层还没被选（说明它在回溯时被撤销过），就跳过当前值——这是"同一层去重"和"同一条路径内允许重复使用"的标准写法，专门用来处理"结果不能重复但输入有重复元素"的题目。

判断能否剪枝的一般原则：如果当前的部分解已经不可能满足最终条件（比如组合总和已经超过目标值，且候选数组已排序），就没必要往下递归——排序后提前 break 而不是 continue，可以把剩下的候选一并跳过，这是回溯题里最常见的可提前终止场景。

递归树的"层"与"树枝"¶

78-子集（位运算）和回溯解法体现了同一个问题的两种视角：回溯是在显式遍历一棵"选或不选"的决策树，每一层对应一个元素，每个分支对应"选"或"不选"；位运算解法是把这棵决策树"压平"成 2^n 个位掩码直接枚举，两者遍历的是同一个搜索空间，只是数据结构不同（显式递归 vs 隐式二进制编码），复杂度分析见位运算。

37-解数独、79-单词搜索 是回溯在二维网格上的应用，区别只是"选择列表"从"剩余候选数字/单词"变成了"当前格子能填的数字"或"下一步能走的方向"，撤销现场对应"把格子清空"或"把访问标记复原"，框架不变。

收账位置：答案住在决策树的哪里¶

同一个回溯框架、同一棵决策树，做题第一步先问：答案以什么资格收录？

把 78 的收账写成 77 惯性的"先 if 出口再 add"，最深的前缀恰好住在 start == n 那一层——在 add 前就 return 了，整个最深子集漏收（[1] → 只剩 []）。

撤销是"兄弟分支之间的隔离墙"（90 漏撤销实测）¶

撤销那行漏写的后果，不总是"立刻崩"——它取决于决策树有没有真分叉：

• 单链树（如 [1,1]、[2,2,2]：去重把每层的兄弟全杀了，每层只剩一个分支）→ path 单调生长、没有兄弟会踩到脏状态，不撤销也碰巧全对；
• 真分叉树（如 [1,2,2]：根层有 1 分支和 2 分支两个兄弟）→ 第一个分支走完没擦，path 带着 [1,2,2] 的脏底进第二个分支 → 根层"[2] 起头"实得 [1,2,2,2]，幻影子集 [1,2,2,2,2]（去重墙挡不住跨分支传染，它只防同层同值），同时真正的 [2]、[2,2] 消失。

实测（90，[1,2,2]，漏撤销）：4 个用例 PASS（全是单链树）、5 个 FAIL（有分叉的）——"单链碰巧对、分叉立刻脏"。撤销不是循环小家务，是下一次递归还"干净起点"的隔离墙。

for 里的三分法：return > break > continue¶

都是提前止损，分辨率从大到小：

选择依据是"后面还有没有机会"：数值单调递增 + 超预算 → 后面全部注定失败 → break；值重复/某段不是回文 → 只是这支白起，不该连坐后面的候选 → continue。

39 里 break（超预算）和 40/90 里 break+continue 同框共存、分工明确——山脉的传染半径不同，不是两个可以混用的东西。

撤销的粒度：你能 new 一张新表吗（90 漏撤销的镜像）¶

撤销只该撤你自己那一笔——做选择是一笔（used[i]=true + path.add），撤销就是同粒度的一笔（used[i]=false + path.remove）。used = new boolean[n]（掀桌重开）不是撤销：它把"分支结束时的全 F 终态"搬到分支进行中的每一步，祖先的 true 是活账（跨层连用合法性的凭据），被一起撕掉后跨层连用锁死失效——47 里 [1,1,1]/[1,2,2] 幻影即此。与 90 的漏撤销互为镜像：撤太少（脏状态跨分支传染）/ 撤太多（活账被误杀）。

本章十题一表（47 收口总结）¶

去重宇宙对照（40/90/47 三胞胎）¶

组合用位置（start）定层，排列用状态（used 是否使用中）定层——同一去重思想的两种载体。