第7章｜回溯与搜索
Unit 06 · LeetCode #40 · 重构版
← Unit 05
40
Combination Sum IISingle Use · Same-Level Dedup
值可以重复，
但输入位置只能使用一次。
remaining 判断目标是否补满；选择一个输入位置后，下一层从它的后一个位置继续；同一父状态下，相同值只允许最靠前的副本开启分支。
题目要求
给定可能含重复值的候选数组 candidates 与目标值 target，返回所有和等于目标值的唯一组合。每个输入索引在一条组合中最多使用一次。
class Solution:
def combinationSum2(self, candidates, target):
pass
- 排序用于建立相邻重复结构，并支持数值上界 break；
- 资源单位是输入索引，而不是数值；
- 同层重复要跳过，同路径中的不同重复索引可以同时使用。
主实验
输入：[10,1,2,7,6,1,5]，target=8
排序：[1₀,1₁,2₂,5₃,6₄,7₅,10₆]
答案：[[1,1,6],[1,2,5],[1,7],[2,6]]
与 #39 的核心差异
#39：当前索引可复用
#40：当前输入位置消耗后不能再用
同时：输入可能重复 → 增加同层去重
Single-use Index
同一个数值可以来自不同索引，但同一索引不能在一条路径中重复出现。
Same-level Dedup
同一父状态下，相同值开启的后续分支与第一个分支等价。
Same-path Duplicate
进入更深层后，另一个相同值索引仍可合法加入路径，例如 [1,1,6]。
Sorted Break
排序后若当前值已超过 remaining，本层后续值也全部不可行。
真实搜索树｜排序后 [1₀,1₁,2₂,5₃,6₄,7₅,10₆] → 8
绿色底边：答案递归状态continue / break 只发生在候选检查，不生成伪节点
当前状态契约
当前路径和0 / 8
当前 path 与来源索引
当前递归栈
当前候选判断链
current[]
start0
remaining8
当前 index—
事件记录
索引不变量
唯一性不变量
当前路径和0
当前 remaining8
已识别答案0 / 4
真实递归节点
状态一致是
渐隐脚手架完整演示 → 功能提示槽位 → 关键代码补全 → 独立完成
关键槽位补全先选左侧槽位 → 再选右侧代码
实时拼接后的代码骨架只拼接你已经建立的语义映射
当前认知焦点
此刻不应该提前改变
本行真正负责
代码 × 状态逐行联动
状态依赖问题｜根层 start=0 扫描 index=1 的第二个 1 时，为什么执行 continue 后真实树里不会出现另一棵 [1] 子树？
这只是理解检查，不会阻塞下一步或自动播放。
独立完成｜关闭上方脚手架后，自行写出 #40
迁移题：LeetCode #491 非递减子序列
#491 不能排序，因为原数组相对顺序就是题意的一部分。迁移重点是：用每层局部 seen 替代“排序后相邻重复”的去重方式。
所有迁移步骤始终可进入
Unit 06 Skill 卡
#40 把资源单位从“值”明确为“输入索引”：下一层只进入更大的索引；同一父状态下再对相同值做去重。迁移到 #491 后不能排序，因此同层去重从相邻判断改为每层独立 seen。
真实树17 个递归状态
答案4 个唯一组合
单次使用下一层从当前索引之后继续
同层去重兄弟相同值只保留第一棵子树
控制流continue / break 不生成节点
#491原顺序 + 每层局部 seen