第7章｜回溯与搜索
Unit 07 · LeetCode #131 · 重构版
← Unit 06
131
Palindrome PartitioningCut End · Validate Segment
选择的不是某个字符，
而是这一段在哪里结束。
进入 backtrack(start) 时，path 已覆盖 s[:start]。本层枚举 end，只有回文片段 s[start:end+1] 才能进入真实递归树；非法片段只发生在候选检查层。
题目模型
将字符串切成若干连续片段，每个片段必须是回文，且所有片段首尾相接完整覆盖输入。
state = start
candidate = s[start:end+1]
next_state = end + 1
candidate = s[start:end+1]
next_state = end + 1
- 答案：["a","a","b"]、["aa","b"]；
- "ab"、"aab" 在递归之前被过滤；
- 非法候选不应被画成递归节点。
核心契约
"".join(path) == s[:start]
all(piece is palindrome for piece in path)
all(piece is palindrome for piece in path)
候选先验证，再 append；真正进入子调用时，current/start/visited/递归栈 才切换到新状态。
Cut-End Choice
一层枚举的是终点 end，而不是孤立字符。
Prefix Coverage
path 拼接必须恰好覆盖 s[:start]。
Feasibility Filter
非回文只被检查和 continue，不进入树。
Complete Consumption
start == len(s) 才记录完整分割。
1. 选择切割终点
2. 回文候选过滤
3. 完整消费与撤销
4. 边界错误实验
5. 渐隐脚手架
6. 迁移 #93
s = "aab"｜真实递归状态树
字符串覆盖
当前 path
当前层候选
递归栈
当前状态
真实树节点
已访问
已记录答案
queue—（DFS递归）
覆盖状态
渐隐脚手架完整演示 → 功能提示槽位 → 关键代码补全 → 独立完成
关键槽位补全先选左侧槽位 → 再选右侧代码
实时拼接后的代码骨架只拼接已建立的语义映射
当前认知焦点
此刻不应该提前改变
本行真正负责
代码 × 状态逐行联动
状态依赖问题｜执行
path.append(piece) 后，哪些状态还不能提前切换到子节点？本题用于检查理解，不会阻塞“下一步”或“自动播放”。
#131 独立完成
迁移题：LeetCode #93 复原 IP 地址
搜索骨架仍是“枚举切割终点 → 验证片段 → append → end+1 → pop”。变化在于片段合法性改为 IP 规则，并增加固定 4 段与容量剪枝。
Unit 07 Skill 卡
字符串分割回溯的核心不是“选字符”，而是枚举下一段终点。非法片段只停留在候选层；真正进入递归节点时才推进 start、current、visited 与递归栈。
状态start + path
候选s[start:end+1]
过滤递归前验证片段
下一层end + 1
树节点只保留真实 backtrack 状态
#93迁移四段 + IP规则 + 容量剪枝