Algorithm · Backtracking
决策树上的系统化枚举：三件套模板 · 子集/排列/组合 · 同层去重与剪枝 —— 把 O(n!) 写出秩序
路径（已做选择）· 选择列表（还能选啥）· 结束条件（收集答案）
子集（start 指针）· 排列（used 数组）· 组合（start + 长度剪枝）
同层去重（排序 + used[i−1]）· 可行性/最优性剪枝 · N 皇后 O(1) 判冲突
Why Backtracking
| 任务 | 答案有多少个 | 你会怎么下手 |
|---|---|---|
| 列出 [1,2,3] 的全部子集 | 2³ = 8 个 | 手算，一分钟列完 |
| 列出 [1..20] 的全部子集 | 2²⁰ ≈ 104 万个 | 想写 20 层 for 循环 —— 写不出来 |
| 列出 [1..30] 的全排列 | 30! ≈ 10³² 个 | 宇宙寿命内跑不完 |
手里是 [1,2,3]，从空集 [] 出发。现在只问一个问题：1 要不要进这个子集？要 → [1]；不要 → []。然后对 2 问一遍，再对 3 问一遍。三个"要不要"问完，8 个答案自然全部出现。回溯的全部动作就是这么一句。
走「要 1」这条路得到 [1,2,3] 之后，还要回到「不要 1」那条路重新走。如果不把刚才加进去的 1 拿掉，第二条路就会带着 1 一起走，答案全错。这个"拿掉最后一步"的动作叫撤销（backtrack，字面意思就是"往回走"），它是这套方法名字的由来。
回溯不消除指数级复杂度——2ⁿ、n! 该多大还是多大。它换来的是三件事：代码能写出来、答案不漏不重、还能剪枝把明显没戏的整棵子树提前砍掉。所以它是"指数问题里最可控的写法"，不是"把指数变成多项式的魔法"。
先把"一步步做决定"画成一棵决策树（下一页的定义 + 图解页）→ 抽出十行模板 → 子集 / 组合 / 排列三个变体 → 最后两页讲去重与剪枝。读完你应该能自己推导出模板，而不是背它。
Prerequisites & Glossary
| 术语 | 一句话理解（先记住这个，细节后面展开） |
|---|---|
| 决策树 decision tree | 把"每一步有哪些选择"画成的树：根是还没做任何决定，每条边是一个决定，每个节点是一个"半成品答案" |
| 路径 path | 从根走到当前节点，沿途做出的全部选择——也就是"到目前为止的部分答案" |
| 选择列表 choices | 站在当前节点上，还能选哪些；这份清单怎么算，决定了是子集 / 组合 / 排列 |
| 结束条件 base case | 什么时候停止往下走：收集答案、或判定这条路作废 |
| 撤销 / 状态恢复 | 返回上一层之前，把这一步加进路径的东西去掉，让兄弟分支拿到干净状态 |
| 剪枝 pruning | 明知整棵子树不可能有答案（或不可能更优）时，提前不再往下走 |
| 解空间 solution space | 所有可能被枚举到的候选答案的总个数；它的大小就是回溯的复杂度（2ⁿ / n! / C(n,k)） |
| DFS 深度优先搜索 | "一条路走到底，走不动了再退回上一个岔口"的遍历顺序；回溯就用它 |
| 同层 vs 树枝 | 同层=同一个父节点下的兄弟分支；树枝=从根往下的一条链。去重时两者语义完全不同 |
先读这几篇再回来。本 deck 默认你已经能读懂 2ⁿ、递归和数组下标：
复杂度分析 → 2ⁿ 与 n! 到底有多大
二叉树 → 决策树就是一棵"每个节点含义不同"的树
栈与队列 → 递归背后那个隐式栈
动态规划 → 只要最值、不要具体方案时的替代方案
把回溯记成一个不断重复的两步动作：① 在当前层，把"还能选的"逐个试一遍，每试一个就往下走一层；② 从下层回来，一定把刚才试的那一步撤掉。后面所有变体（子集 / 组合 / 排列 / 棋盘 / 去重 / 剪枝）都不改这个动作，只改"还能选的"这份清单怎么算。
去重那一页的所有困惑都来自把这两件事混为一谈：树枝上要禁止"同一个元素用两次"（模板自带），同层里要禁止"选相同的值"（需要额外判断）。两个"重复"含义不同，代码写法也不同。
Decision Tree Walk
上面那三个"要不要"的问题，画出来就是一棵树：每个岔口是一个决定，从根走到任何一个节点，沿途的选择连起来就是一个候选答案。
把问题建模成"每一步有若干选择"的决策树，用 DFS 走遍所有分支；走不通或收集完答案就撤销最后一步、换下一个分支——"回"的是状态，"溯"的是路径。
① 路径 path：已经做出的选择；② 选择列表：当前还能选什么；③ 结束条件：路径满足答案形态时收集（或提前剪枝返回）。
DFS 是遍历方式，回溯是遍历+状态恢复的算法框架：DFS 走图/树是"访问完就完"，回溯必须"撤销现场"让兄弟分支拿到干净状态。
要所有方案 / 具体方案 → 回溯（方案数指数个，没法压缩）；只要最值/计数且满足无后效性 → DP（DP deck）。
决策树节点数就是复杂度：子集 2ⁿ、排列 n!、组合 C(n,k)——指数不可避免，能做的是剪枝减树。
| 问题形态 | 解空间 | 典型题 |
|---|---|---|
| 子集（每个元素选/不选） | O(2ⁿ) | 78/90/131 分割回文串 |
| 排列（顺序敏感） | O(n!) | 46/47/60 |
| 组合（定长不排序） | O(C(n,k)) | 77/39/40/216 |
| 棋盘/网格放置 | 指数+剪枝 | 51 N 皇后/37 数独/79 单词搜索 |
| 图/隐式图搜索 | 状态空间 | 332 重新安排行程 |
Subset Tree · [1,2,3]
The Ten-Line Frame
var ( res [][]int path []int ) func backtrack(choices, start int) { // 1. 结束条件：收集答案 if 满足条件 { res = append(res, append([]int{}, path...)) // 拷贝! // 不要 return：子集题要继续 } // 2. 遍历选择列表 for i := start; i < n; i++ { // 3. 剪枝 + 做选择 path = append(path, a[i]) backtrack(i+1) // 下一层 path = path[:len(path)-1] // 撤销 } }
每个节点都是答案（子集）→ 收集后不返回；只叶子是答案（组合定长）→ 长度够了 return；找到即停（数独）→ 找到后层层 return true。
三种形态：start 指针往后（子集/组合，防重复选）；used 数组（排列，位置无关）；棋盘坐标（N 皇后）。选择列表的维护方式就是题型的签名。
Go 经典坑：res = append(res, path) 存的是底层数组引用，撤销后 res 里全变——必须拷贝一份。这是 Go 岗专属送命题。
path 用切片共享底层数组（append 撤销配对）；若用值传递每层拷贝，代码简单但开销大——面试说清取舍。
Subsets · Permutations · Combinations
每个元素"选/不选"，答案在每个节点。start 保证只往后选——树的右侧天然排除已处理元素，不需要 used。
顺序敏感，每层都能从头选（除了已在路径里的）→ used[i] 标记占用。结束条件：len(path)==n 只在叶子收。
= 子集 + 定长 k。剪枝：i <= n−(k−len(path))+1——剩下元素不够凑满 k 就别进循环了，把"到叶子才发现不行"提前到"进循环前"。
子集无限制、组合限长度、排列乱顺序——三句话对应 start / start+剪枝 / used 三种维护。写题先问自己属于哪个模板。
| 维度 | 子集 78 | 组合 77 | 排列 46 |
|---|---|---|---|
| 选择列表 | start..n | start..n（剪枝） | 全部非 used |
| 答案位置 | 每个节点 | 长度 == k | 叶子（长度 n） |
| 去重手段 | start 天然去重 | start + 同层去重 | used + 同层去重 |
| 复杂度 | O(2ⁿ·n) | O(C(n,k)·k) | O(n!·n) |
| 输入要求 | — | 有序更好剪 | 有重复才需排序 |
Dedup · LC 90/47/40
// 90 子集 II：输入含重复元素 sort.Ints(a) // 前提：先排序！ func backtrack(start int) { res = append(res, copyOf(path)) for i := start; i < len(a); i++ { // 同层去重：与前一个值相同 // 且前一个在本层被跳过 if i > start && a[i] == a[i-1] { continue } path = append(path, a[i]) backtrack(i + 1) path = path[:len(path)-1] } } // 47 排列去重（used 版）： if used[i] || (i > 0 && a[i] == a[i-1] && !used[i-1]) { continue }
① 树枝去重（同一元素不能用两次）：子集/组合用 start、排列用 used——这是模板自带的；② 同层去重（同一层不选相同的值）：本页的主角，解决"输入有重复"。
排序后同值元素相邻：本层若第二次选同值，产生的子树与第一次完全相同 → 只保留"同值第一个"的分支。i>start 保证"第一个"不被跳过。
used[i−1]==true 说明 a[i−1] 在树枝上（当前路径）——可用；false 说明在同层被回撤——同值必重。两种写法（!used 与 used）都行，方向不同而已，但要与排序配合。
同层去重依赖"同值相邻"——忘记 sort 是该族题的头号 bug。复杂度：去重后树规模 = 不同答案数，最坏仍 2ⁿ。
Pruning · LC 51/37/79
① 可行性剪枝：当前部分解已违反约束 → 整棵子树砍掉（N 皇后冲突、组合和超限）；② 最优性剪枝：当前代价已 ≥ 已知最优 → 不用走完（TSP、记忆化中的界限）。剪枝越靠上层省得越多。
三组集合：cols（列）、diag1（row−col，↘ 方向同值）、diag2（row+col，↙ 方向同值）——按行递归，每行只试 n 列，冲突判定全 O(1)。n=9 时解 352 个，纯暴力 + O(1) 判定即可过。
行/列/九宫三个 bool 矩阵记录占用；填充时找"候选最少"的空格先试（MRV 启发式）能大幅剪枝；解唯一 → 找到后层层返回 true。
网格 DFS + 原地标记（把走过格子改字符 / 用位掩码）替代 visited 数组，回溯时还原——"原地标记+恢复"是网格回溯的标准姿势（Trie 协同见 LC 212）。
| 题 | 状态表示 | 剪枝要点 |
|---|---|---|
| 51 N 皇后 | 三个集合（列/两对角） | O(1) 判冲突；按行放置天然无行冲突 |
| 37 解数独 | 行/列/宫 bool 矩阵 | MRV：先填候选最少的格 |
| 79 单词搜索 | 网格原地标记 | 首字母过滤 + 长度剪枝 |
| 39/40 组合总和 | 路径 + 剩余 target | 排序后 break（39 可重复）/同层去重（40） |
| 131 分割回文串 | 子串起点 | 回文 DP 预判表 O(1) 判回文 |
LeetCode Shortlist
| 阶段 | 题目（编号 · 难度） | 要点 |
|---|---|---|
| 模板三连 | 78 子集 M · 77 组合 M · 46 全排列 M | 三大模板各默写一遍 |
| 去重进阶 | 90 子集 II M · 47 全排列 II M · 40 组合总和 II M | 排序 + 同层去重统一套路 |
| 棋盘与剪枝 | 51 N 皇后 H · 37 解数独 H · 79 单词搜索 M | O(1) 冲突判定 / 原地标记 |
| 综合应用 | 39/216 组合总和 M · 131 分割回文串 M · 22 括号生成 M · 332 行程 H | 131 需回文 DP 预处理；332 是欧拉路径 |
Cheat Sheet
func backtrack(选择列表, path) { if 满足结束条件 { res = append(res, append([]int{}, path...)) // 拷贝! return // 子集题不 return } for _, c := range 选择列表 { path = append(path, c) // ① 做选择 backtrack(新选择列表, path) path = path[:len(path)-1] // ② 撤销（必成对） } }
| 树枝去重 | 同一个元素不能在同一条路径上用两次 —— 子集/组合靠 start、排列靠 used，模板自带 |
| 同层去重 | 先排序，再 i > start && a[i] == a[i-1] 跳过；排列版是 !used[i-1] |
| 组合剪枝 | 剩下元素不够凑满 k 就别进循环：i <= n-(k-len(path))+1 |
| 维度 | 子集 78 | 组合 77 | 排列 46 |
|---|---|---|---|
| 选择列表 | start..n | start..n+剪枝 | 全部非 used |
| 答案位置 | 每个节点 | 长度 == k | 叶子（长度 n） |
| 去重手段 | start 天然去重 | start + 同层去重 | used + 同层去重 |
| 复杂度 | O(2ⁿ·n) | O(C(n,k)·k) | O(n!·n) |
1 · 答案拷贝了吗？Go 里 append(res, path) 存的是切片引用，撤销后全被改掉——必须 append([]int{}, path...)。Go 岗专属送命题。
2 · 结束条件的位置对吗？子集每节点收且不 return；组合够长才收；数独/单词搜索找到即层层 return true。
3 · 选择列表怎么算？子集与组合用 start 只往后看（天然去掉顺序重复），排列用 used 跳过已占用。
4 · 同层去重前排序了吗？a[i]==a[i-1] 依赖"同值相邻"，忘记 sort 是该族题的头号 bug。
5 · 树枝与同层分清了吗？树枝禁"同一元素用两次"，同层禁"选相同的值"——两个"重复"不是一回事。
Interview QA
先自答，再对照：每题先说出你的答案（哪怕只说关键词），再展开看下面那行——想不出来的时候别急着看，卡住的那 30 秒才是真正长记性的部分。
DFS 是遍历方式；回溯 = DFS + 状态恢复（做选择/撤销选择成对）。图 DFS 不需要撤销（visited 永真），回溯的 visited 是"当前路径"语义，要还原。
子集：start 指针、每节点收答案；组合：start + 定长剪枝、长度够才收；排列：used 数组、每层可从头选。口诀"组合=子集+定长、排列=子集−start"。
从 i 开始还剩 n−i+1 个可选元素，还差 k−len 个位置：n−i+1 ≥ k−len ⇒ i ≤ n−(k−len)+1。超过它连叶子都凑不齐，整段 for 直接不进。
排序使同值相邻；本层第二个同值元素的子树与第一个完全重复 → 跳过。i>start（或排列版 !used[i−1]）保护"本层第一个同值"不被误跳。
cols[c]、diag1[r−c]、diag2[r+c] 三个 map/数组：同列、同 ↘ 对角（差相等）、同 ↙ 对角（和相等）各一查一插。按行递归天然消除行冲突。
树节点数 × 每节点代价：子集 O(2ⁿ·n)（拷贝 path）、排列 O(n!·n)、组合 O(C(n,k)·k)。先说"决策树多大"再说"拷贝代价"。
path 是共享底层数组的切片，append(res, path) 存引用——回溯撤销后 res 里的"答案"全被改掉。必须 append([]int{}, path...) 拷贝。这是 Go 岗专属高频坑。
要所有/具体方案、约束复杂难建模 → 回溯；只要最值/计数且无后效性 → DP。分界案例：全排列（回溯）vs 最长递增子序列（DP）；括号生成两法皆可但回溯更自然。
Related & References
参考来源（本 deck 结论可溯源至下列一手材料）
| LeetCode 78/77/46/90/47/51/37/79/131 官方题解 | 三大模板、同层去重、棋盘剪枝的标准表述 |
| S. Skiena · The Algorithm Design Manual（回溯章节） | 剪枝分类与回溯系统化设计 |
| oi-wiki.org/search/backtracking · 递归/剪枝优化 | 剪枝四类（可行性/最优性/搜索顺序/记忆化） |
| Go 官方 FAQ · slices and array internals | append/切片共享底层数组导致 res 污染的语义依据 |