第7章｜回溯与搜索

Unit 11 · Comprehensive Review · 重构版

← Unit 10

回溯不是一段固定代码，
而是一套可迁移的搜索建模语言。

面对新题时，先定义 State、Choice、Constraint、Goal、Pruning、Modify、Recurse、Undo 与 Snapshot。代码只是这些状态契约的编译结果。

State当前决定了什么
Choice下一步能选什么
Constraint候选是否合法
Goal何时形成答案
Pruning哪些分支必失败
Modify选择怎样改状态
Recurse何时真正进入子状态
Undo返回后恢复什么
Snapshot如何冻结答案
1. 模型识别
2. 作用域辨析
3. 三道门
4. 症状反推
5. 渐隐脚手架
6. 迁移 #22
综合实验
当前建模结论
当前状态契约

学习事件记录

State
Choice
Goal
Undo
主要风险
代表题
完整演示功能提示槽位关键代码补全独立完成
关键槽位补全先选槽位 → 再选代码
实时拼接后的代码骨架


当前认知焦点随逐行轨迹变化
代码 × 状态逐行联动真实 DFS · queue 不存在
绿：已进入橙：current紫：pending底绿：答案


状态依赖问题
运行到关键返回点时，这里会出现一个不阻塞轨迹的问题。


#11 综合模板｜独立完成




综合迁移：LeetCode #22 括号生成
资源从“有限输入索引”变成“左右括号预算”。不再需要 used/visited；合法性由 opened 与 closed 的前缀关系维护。
当前步骤 1/4最大已解锁步骤 4/4所有迁移步骤始终可进入


保持不变
State → Choice → Constraint → Goal → Modify → Recurse → Undo → Snapshot 的执行链仍然存在。
发生变化
没有输入索引资源，不需要 used；状态由 path、opened、closed 就足够描述。


前缀约束
左括号：只有 opened < n 时可选。
右括号：只有 closed < opened 时可选。

因此根状态 opened=closed=0 时，右括号只会停留在“候选条件失败”，不会进入递归树。


#22 迁移语义槽位左语义 · 右纯代码
实时拼接后的代码骨架


当前认知焦点#22 n=3
代码 × 状态逐行联动22 个真实递归状态
非法前缀不建节点答案 5 个
状态依赖问题
根状态为什么不能把 ) 作为递归子节点？
#22 完整提交代码




第7章终章总结
模板不是答案。真正可迁移的是：先定义资源单位和状态作用域，再让 Constraint、Goal、Recurse 与 Undo 精确维护同一个搜索空间。候选被拒绝不等于进入递归节点；发起调用也不等于已经进入子状态。