第7章｜回溯与搜索
Unit 04 · LeetCode #90 · 优化版
← Unit 03
90
Subsets IISort · Same-level Dedup
重复值可以进入同一条路径，
但不能在同一层复制整棵子树。
排序把相同值放到相邻位置。回溯扫描当前候选窗口时，只跳过同一父状态下的后续相同值；进入下一层后，后一个副本仍可被选择，因此 [2,2] 不会丢失。
LeetCode #90 题目模型输入可重复，输出子集必须唯一
题目要求
给定一个可能包含重复元素的整数数组 nums，返回所有可能的子集，结果中不能包含重复子集。
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
pass
- 每个搜索节点仍代表一个合法子集；
- 输入值可以重复，但输出路径值序列必须唯一；
- 本页使用
[1,2,2]观察同层与同路径的区别。
核心条件
nums.sort()
if index > start and nums[index] == nums[index - 1]:
continue
if index > start and nums[index] == nums[index - 1]:
continue
index > start 把重复判断限定在当前递归层；当 index == start 时，即使值与前一个相同，也允许形成 [2,2]。
Canonical Sort
先排序，使相同值相邻，局部条件才能识别等价候选。
Same-level Duplicate
同一父状态下，相同值作为分支起点会生成等价后代，只保留第一个。
Same-path Duplicate
不同深度可以连续选择相同值，形成合法子集 [2,2]。
index > start
表示当前候选不是本层第一个位置，是去重范围的关键边界。
1. 等价分支
2. 排序相邻
3. 同层跳过
4. 错误条件实验
5. 渐隐脚手架＋逐行联动
6. 迁移 #47
环节 1/6
nums=[1,2₁,2₂]｜子集状态空间观察重复分支
状态空间树
当前递归层
状态变量
path[]
start0
index—
判断结果尚未判断
skip = index > start
and nums[index] == nums[index - 1]
本层候选
已确认的唯一子集
当前状态解释
子集 II 搜索契约
三个位置条件
搜索事件记录
当前 path[]
当前 start0
当前 index—
是否同层重复未判断
记录时机进入每个调用后记录
下一层index + 1
唯一性不变量
完整性不变量
唯一子集1 / 6
当前深度0
本层候选数3
已跳过分支0
当前规则待判断
切换三个实验，观察被破坏的范围。
完整演示→
功能提示槽位→
关键代码补全→
独立完成
脚手架只减少提示，不限制环节切换。
关键槽位补全先选槽位 → 再选代码
待填槽位（只提示作用）
待选代码标签
实时拼接后的代码骨架0 / 6
当前认知焦点
当前递归栈
代码 × 状态逐行联动每一步只更新真实发生的状态
图状态
状态依赖问题
到达关键状态时，这里会出现问题；它不会阻塞下一步或自动播放。
独立完成关闭提示后，从算法契约自行写出完整代码
第7章 Unit 04 Skill 卡
子集 II 的去重对象不是“重复值”，而是同一递归层中的等价选择。排序建立相邻结构，index > start 限定同层范围；进入下一层后，重复副本仍可继续使用。
主状态path + start
预处理nums.sort()
同层去重index>start 且值等于前值
同路径重复index==start 时允许继续选择
记录时机每个搜索节点立即记录
#47 增量用 not used[index-1] 表达同层
复杂度最坏 O(n·2ⁿ)
常见错误index>0、不排序、全局禁值
下一题#39 组合总和
本环节已完成完成状态已记录；所有环节始终可以自由切换。