UNIT 01枚举目标
#78 子集
- 状态与选择
- 已选路径与下一可选起始索引；后续索引递增。
- 记录与终止
- 每个搜索节点都是一个合法子集，都需要记录独立快照。
- 合法性与剪枝
- 不施加额外长度限制，索引递增避免顺序重复。
- 恢复与不变量
- 子调用结束撤销当前选择，父状态恢复到调用前。
迁移 · #1863 所有子集的异或总和异或总和改变节点的贡献聚合方式，搜索空间保持不变。
先说清契约，再独立实现进入本单元 ↗
第7章｜回溯与搜索
Unit 00 · 回溯与状态空间搜索基础
← 第6章 Unit 11
U00
Backtracking FundamentalsState · Choice · Prune · Undo
回溯不是“递归加一个 pop”，
而是可恢复状态上的系统搜索。
每个调用代表一个搜索状态，每条调用边代表一次选择。你必须明确当前状态、合法选择、记录时机、终止条件、剪枝依据，以及返回父层前如何恢复共享状态。
统一骨架
def backtrack(state):
if should_record(state):
record_snapshot(state)
if should_stop(state):
return
for choice in choices(state):
if violates_constraint(state, choice):
continue
make_choice(state, choice)
backtrack(next_state)
undo_choice(state, choice)
后续题型只是在替换“状态变量”
子集/组合常用 start 消除顺序重复；排列常用 used；网格搜索维护 visited；N 皇后/数独维护列、对角线或候选集合。骨架不变，状态契约变化。
子集 / 组合path + start；每个节点或固定深度记录。
排列path + used；同一层选择尚未使用元素。
网格搜索坐标 + visited；进入标记，离开恢复。
约束放置列与对角线集合；冲突即剪枝。
已恢复上次学习位置本次草稿已保留
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 括号生成从输入索引资源转为括号数量资源，重新推导候选而非照搬模板。
先说清契约，再独立实现进入本单元 ↗
共享路径 path
已记录答案快照
当前状态契约
递归调用栈
状态事件
进入不变量
恢复不变量
当前 path[]
当前 start0
调用栈深度1
已记录答案1
状态是否干净是
错误实验：共享可变状态会同时污染未来分支与历史答案
七个语义槽位记录、终止、选择、递归与恢复
代码—调用栈—path—答案联动微型搜索：[1,2,3]，深度≤2
当前状态问题
保留什么
仍然使用 path、start 和递增索引；进入每个调用后立即记录 path.copy()。
#78 六个变化槽位从通用骨架迁移
迁移脚手架
题目要求所有子集，所以空路径也是答案；每次进入调用先记录。start保证下一层只选择更靠后的元素，避免同时出现 [1,2] 与 [2,1]。
#78 运行轨迹nums=[1,2]
LeetCode #78 完整提交代码
编辑器会保存高度与内容。检查器关注状态契约、索引推进和撤销，不要求逐字符一致。
第7章 Unit 00 能力地图
回溯的稳定解题方式，是先写清状态契约，再决定选择、记录、终止、剪枝和恢复。代码中的 append → recurse → pop 只是该契约的一种实现。
状态足以决定候选与后续转移的最小信息
记录保存快照，不等于停止搜索
终止完成后不再深入，未必是剪枝
剪枝根据约束证明后代不可能成功
共享修改append、used、visited、约束集合
恢复pop、取消标记、移除约束
本环节已完成
先停留观察当前状态，继续按钮稍后可用。