UNIT 01枚举目标
#78 子集
- 状态与选择
- 已选路径与下一可选起始索引；后续索引递增。
- 记录与终止
- 每个搜索节点都是一个合法子集，都需要记录独立快照。
- 合法性与剪枝
- 不施加额外长度限制，索引递增避免顺序重复。
- 恢复与不变量
- 子调用结束撤销当前选择，父状态恢复到调用前。
迁移 · #1863 所有子集的异或总和异或总和改变节点的贡献聚合方式，搜索空间保持不变。
先说清契约，再独立实现进入本单元 ↗
第7章｜回溯与搜索
Unit 00 · 回溯与状态空间搜索基础
← 第6章 Unit 11
U00
Backtracking FundamentalsState · Choice · Prune · Undo
回溯不是“递归加一个 pop”，
而是可恢复状态上的系统搜索。
每个递归调用代表一个状态；每条边代表一次选择；约束决定哪些分支不值得继续；返回父状态前必须撤销本层对共享状态造成的修改。
本单元目标
通过最小实验“从候选 `[1,2,3]` 中构造长度不超过2的路径”，拆解回溯中的六个独立问题：
- 当前状态由什么数据表示？
- 当前层有哪些合法选择？
- 何时记录答案或终止？
- 什么条件可以剪枝？
- 做出选择后修改了什么？
- 返回上一层前必须恢复什么？
统一骨架
def backtrack(state):
if is_complete(state):
record_answer(state)
return
for choice in available_choices(state):
if violates_constraint(state, choice):
continue
make_choice(state, choice)
backtrack(state)
undo_choice(state, choice)
State 状态
足以描述“当前搜索走到哪里、已经做了什么选择、哪些候选仍可用”的最小信息集合。
State-Space Tree
节点是状态，边是选择，根是初始状态，叶子可能是答案、失败状态或被剪枝状态。
Pruning 剪枝
依据约束证明某个分支不可能产生目标答案，因此不再展开其后代。
Undo 撤销
把共享状态恢复到进入当前递归层之前的样子，使兄弟分支从正确父状态开始。
CHAPTER 07 / THE COGNITIVE ATLAS
第 7 章 · 认知梯度全景图
回溯与搜索：在选择、探索与撤销中，构建完整的状态空间。
贯穿本章的统一框架状态 → 候选 → 选择 → 递归 → 恢复。分开定义什么时候记录、什么时候终止，以及哪些分支不合法。
从基础到复合任务，每一步增加一种决策
这里的梯度描述认知任务的递进，不等同于题库的难度标签。点击题目可进入对应单元。
起点 · Unit 00 回溯与状态空间搜索。先理解状态、操作与不变量，再沿下列路线练习。
- 01
- 02
- 03
- 04
- 05
每道题在框架中的具体形式
用同一组问题定位每个单元，再观察迁移题改变了哪个条件。进入写代码环节后，学习地图会收起，留出独立思考的空间。
UNIT 02枚举目标
#77 组合
- 状态与选择
- 当前组合、起始数字与还缺的选择数量。
- 记录与终止
- 长度达到 k 时记录，之后不再深入。
- 合法性与剪枝
- 候选不足以填满剩余位置时可提前终止。
- 恢复与不变量
- 路径中的索引递增，退出子调用时恢复路径。
迁移 · #216 组合总和 III组合总和 III 额外维护和值，合法性同时受长度和目标和约束。
先说清契约，再独立实现进入本单元 ↗
UNIT 03枚举目标
#46 全排列
- 状态与选择
- 已排顺序与每个输入索引是否被当前路径使用。
- 记录与终止
- 路径使用全部输入索引后记录完整排列。
- 合法性与剪枝
- 每层可以选择任意尚未使用的索引，顺序不同是不同答案。
- 恢复与不变量
- 退出时同时撤销路径元素与使用标记。
迁移 · #47 全排列 II全排列 II 在索引使用限制之外增加同层重复值的控制。
先说清契约，再独立实现进入本单元 ↗
UNIT 04重复与资源
#90 子集 II
- 状态与选择
- 排序输入、递增起始索引和当前子集。
- 记录与终止
- 每个节点记录子集，直到没有后续候选。
- 合法性与剪枝
- 同层相同值只开一个分支，同路径仍可使用不同的相同值索引。
- 恢复与不变量
- 撤销路径后恢复父状态，不能把重复值全部禁止。
迁移 · #47 全排列 II全排列 II 没有递增窗口，需借助使用标记表达同层去重。
先说清契约，再独立实现进入本单元 ↗
UNIT 05重复与资源
#39 组合总和
- 状态与选择
- 当前组合、下一候选起点与剩余目标和。
- 记录与终止
- 剩余目标和为零时记录，超过目标的分支停止。
- 合法性与剪枝
- 同一候选可以重复选，索引顺序消除组合顺序重复。
- 恢复与不变量
- 每次选择改变路径与剩余和，返回后恢复父层契约。
迁移 · #40 组合总和 II组合总和 II 每个输入索引只能选一次，并增加同层去重。
先说清契约，再独立实现进入本单元 ↗
UNIT 06重复与资源
#40 组合总和 II
- 状态与选择
- 排序输入、起始索引、组合路径与剩余目标和。
- 记录与终止
- 达到目标记录；剩余和不足以接纳候选时不再深入。
- 合法性与剪枝
- 下一层从后续索引选择，同层跳过重复值，但允许跨层使用不同重复索引。
- 恢复与不变量
- 撤销当前选择，输入索引在一路中至多使用一次。
迁移 · #491 非递减子序列非递减子序列不能排序，用每层独立的已选值集合完成同层去重。
先说清契约，再独立实现进入本单元 ↗
UNIT 07结构化选择
#131 分割回文串
- 状态与选择
- 已经切出的片段与尚未切割的后缀入口。
- 记录与终止
- 起点到达字符串末尾时记录一组完整分割。
- 合法性与剪枝
- 只选择当前起点开始的回文片段。
- 恢复与不变量
- 返回时移除最后一段，始终恰好覆盖已处理前缀。
迁移 · #93 复原 IP 地址IP 地址改为四段数字，增加段长度、数值范围和前导零约束。
先说清契约，再独立实现进入本单元 ↗
UNIT 08结构化选择
#79 单词搜索
- 状态与选择
- 网格坐标、已匹配字符位置与当前路径访问标记。
- 记录与终止
- 完整单词匹配后返回存在性结果。
- 合法性与剪枝
- 只走相邻未使用格，检查越界与字符一致性。
- 恢复与不变量
- 探索失败或需要继续其他分支时恢复访问标记。
迁移 · #212 单词搜索 II多个单词用字典树共享前缀，搜索状态加入字典树节点。
先说清契约，再独立实现进入本单元 ↗
UNIT 09多约束放置
#51 N 皇后
- 状态与选择
- 当前行、已占列与两种对角线集合。
- 记录与终止
- 所有行均已合法放置时记录棋盘。
- 合法性与剪枝
- 选择列时同时检查列与两条对角线冲突。
- 恢复与不变量
- 离开分支时撤销棋子及全部占用关系。
迁移 · #52 N 皇后 IIN 皇后 II 保留合法放置搜索，只累计数量，不构造棋盘列表。
先说清契约，再独立实现进入本单元 ↗
UNIT 10多约束放置
#37 解数独
- 状态与选择
- 待填空格、棋盘与行、列、宫的已用数字。
- 记录与终止
- 全部空格填好时成功；成功后保留完整棋盘。
- 合法性与剪枝
- 候选必须同时满足三类约束，失败时换候选。
- 恢复与不变量
- 失败分支恢复棋盘和约束，成功结果不能被继续撤销。
迁移 · #36 有效的数独有效数独删除搜索过程，只校验当前非空数字是否冲突。
先说清契约，再独立实现进入本单元 ↗
UNIT 11统一契约复盘
回溯与搜索综合复盘
- 状态与选择
- 复盘状态契约；括号迁移使用路径及已用左右括号数量。
- 记录与终止
- 使用完 n 对括号时记录完整答案。
- 合法性与剪枝
- 任何前缀右括号不能多于左括号，左括号不能超过 n。
- 恢复与不变量
- 选择后恢复路径，数量信息随父调用重新确定。
综合迁移 · #22 括号生成从输入索引资源转为括号数量资源，重新推导候选而非照搬模板。
先说清契约，再独立实现进入本单元 ↗
1. 状态、路径与搜索树
2. Choose—Recurse—Undo
3. 完成条件与剪枝
4. 漏撤销与共享引用错误
5. Python模板与完整轨迹
6. 子集题迁移
微型搜索：从[1,2,3]构造长度≤2的递增路径每个节点都可能记录为答案
状态空间树
递归调用栈
共享路径 path
已记录答案
根状态：path=[]，start=0。
当前状态解释
path保存已经做出的选择；start限制下一层只能选择更靠后的索引。
回溯状态契约
进入 backtrack(start) 时，path表示从根到当前节点的选择序列；返回前必须恢复到调用者进入子分支前的状态。
当前 path[]
当前 start0
候选索引0,1,2
当前递归深度0
完成条件每个节点都可记录
撤销动作path.pop()
搜索事件记录
路径不变量
path 恰好表示根到当前搜索节点的选择；其中元素索引严格递增。
恢复不变量
子调用结束后，执行 path.pop()，使父调用继续下一个兄弟选择时看到原来的父状态。
已访问状态数1
当前深度0
已剪枝分支0
已记录答案1
状态是否干净是
记录答案表示当前状态满足输出要求；终止表示不需要继续深入；剪枝表示依据约束证明后续不可能产生目标答案。三者可能同时发生，也可能彼此独立。
路径、访问标记和约束集合通常被多个递归调用共享。修改之后若不恢复，或记录答案时不复制，会让兄弟分支和历史答案同时被污染。
错误一：忘记 path.pop()
子分支留下的元素进入兄弟分支，导致路径不再对应当前树节点。
错误二：result.append(path)
所有答案卡片引用同一个列表对象，后续修改会同步改变历史答案。
错误三：把 return 都当剪枝
正常完成、失败返回、找到一个解后提前结束，与约束剪枝的语义不同。
可以为每个子调用构造新状态，也可以共享一份状态并显式撤销。前者更直观但复制成本更高；后者更高效，但必须严格维护恢复不变量。
新状态写法
backtrack(path+[x])
无需pop但会复制
backtrack(path+[x])
无需pop但会复制
共享状态写法
append→recurse→pop
空间更紧凑
append→recurse→pop
空间更紧凑
找到一个解
可沿调用栈提前返回
不一定收集所有答案
可沿调用栈提前返回
不一定收集所有答案
补全通用回溯模板微型递增路径搜索
def enumerate_paths(nums):
result = []
path = []
def backtrack(start):
if len(path) == 2:
for index in range(start, len(nums)):
backtrack(0)
return result
def enumerate_paths(nums):
result = []
path = []
def backtrack(start):
result.append(path.copy())
if len(path) == 2:
return
for index in range(start, len(nums)):
path.append(nums[index])
backtrack(index + 1)
path.pop()
backtrack(0)
return result
复制状态版本：
def backtrack(start, path):
result.append(path)
if len(path) == 2:
return
for index in range(start, len(nums)):
backtrack(
index + 1,
path + [nums[index]],
)
这个版本不需要undo，因为每个调用拥有自己的path对象；但每条边都会创建新列表。
代码—调用栈—path—答案集合联动完整搜索[1,2,3]
1def enumerate_paths(nums):
2 result = []
3 path = []
5 def backtrack(start):
6 result.append(path.copy())
8 if len(path) == 2:
9 return
11 for index in range(start, len(nums)):
12 path.append(nums[index])
13 backtrack(index + 1)
14 path.pop()
16 backtrack(0)
17 return result
轨迹依次经历记录根状态、选择1、深入[1,2]、撤销2、选择3、撤销1，再处理以2和3开头的兄弟分支。
完成代码联动后进入 LeetCode #78 子集迁移代码正确、查看答案、一键填入或播放完整轨迹后解锁。
迁移题：LeetCode #78 子集
删除“路径长度最多为2”的限制，使搜索遍历所有递增索引路径。关键判断：子集题中每个搜索节点都是一个合法答案，所以进入调用后立即复制path。
第7章 Unit 00 Skill卡
回溯的核心不是递归语法，而是状态契约：进入调用时状态代表当前树节点；选择后进入子状态；返回父层前恢复共享状态；记录答案时复制快照；剪枝必须有明确约束依据。
状态描述当前节点所需的最小信息
选择当前层可扩展的候选分支
完成条件何时构成答案、何时应停止深入
剪枝证明某分支不可能产生目标答案
修改append、标记visited、加入约束集合
撤销pop、取消visited、移出约束集合
答案快照result.append(path.copy())
调用栈语义每层递归对应状态空间树的一个节点
推荐下一题#78 子集：每个搜索节点都可记录