《Hello 算法》子集和 IIPython 回溯解法与四重剪枝策略详解【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇以《Hello 算法》回溯源图 codes/pythontutor/chapter_backtracking/subset_sum_ii.md 内嵌的子集和 II 回溯代码为主体结合仓库中的 Python 参考实现与图解文档系统讲解“数组含重复元素、每个元素只可选一次”这一约束下的回溯解法读者读完后将掌握start游标与“同层相等元素跳过”这两类去重手段的配合方式能独立推导、复现并调试该算法的四重剪枝逻辑。问题定义从子集和 I 到子集和 II子集和 II 的完整题述见 子集和问题文档 的“考虑重复元素的情况”一节给定一个正整数数组nums和一个目标正整数target请找出所有可能的组合使得组合中的元素和等于target。给定数组可能包含重复元素每个元素只可被选择一次。请以列表形式返回这些组合列表中不应包含重复组合。它与子集和 I 的差异决定了两个新增约束数组可能含重复元素例如输入[4, 4, 5]时两个值相同的4各自产生一条搜索分支若不干预会输出[4, 5]和[4̂, 5]两条重复子集4̂表示第二个 4每个元素只能被选择一次而子集和 I 中元素可无限次复用下一轮遍历从i开始本题必须从i 1开始。重复子集的产生根源重复的直接原因是相等元素在同一轮中被分别选作分支根。以[4, 4, 5]、target 9为例第一轮三个选择中有两个都是4它们各自向下展开后都会命中[4, 5]这条解从而在结果列表中输出两条完全相同的子集。因此解法的核心思路是限制相等元素在每一轮同一层中只能被选择一次。四重剪枝策略总览subset_sum_ii的回溯函数中一共布置了四种剪枝操作。下表以 Python 参考实现 为准列出每种剪枝的位置、代码形态与作用。剪枝代码位置代码作用剪枝一循环体内if target - choices[i] 0: break数组已排序当前元素选完即超target时右边元素更大本轮循环直接终止剪枝二循环起点for i in range(start, ...)从start开始遍历避免生成顺序不同的重复子集如[4,5]与[5,4]剪枝三递归调用backtrack(..., i 1, ...)下一轮从i 1开始避免重复选择同一个元素子集和 II 新增约束剪枝四循环体内if i start and choices[i] choices[i - 1]: continue同层去重当前元素与左边元素相等时说明该分支已在本轮生成过直接跳过注意剪枝一与剪枝四对排序的依赖正因为subset_sum_ii入口处先执行了nums.sort()相等元素才必然相邻剪枝四只需与左邻居比较即可排序也使元素单调不减剪枝一才能用break而非continue安全地终止整轮循环。一个值得玩味的细节在 C 版实现 中剪枝一写成了continue而非break。两种写法在正确性等价的前提下break能少做若干次无意义的循环迭代Python 版采用break是更优的写法。完整代码subset_sum_ii 的 Python 实现子集和 II 可视化源文件 内嵌的是一份可直接投喂给 Python Tutor 单步执行的脚本文件头部以!-- [file]{subset_sum_ii}-[class]{}-[func]{subset_sum_ii} --标注了所对应的源文件与函数。这段代码与仓库中的 Python 参考实现 逐行一致此处完整给出并加注说明def backtrack( state: list[int], target: int, choices: list[int], start: int, res: list[list[int]] ): 回溯算法子集和 II # 子集和等于 target 时记录解 if target 0: res.append(list(state)) return # 遍历所有选择 # 剪枝二从 start 开始遍历避免生成重复子集 # 剪枝三从 start 开始遍历避免重复选择同一元素 for i in range(start, len(choices)): # 剪枝一若子集和超过 target 则直接结束循环 # 这是因为数组已排序后边元素更大子集和一定超过 target if target - choices[i] 0: break # 剪枝四如果该元素与左边元素相等说明该搜索分支重复直接跳过 if i start and choices[i] choices[i - 1]: continue # 尝试做出选择更新 target, start state.append(choices[i]) # 进行下一轮选择 backtrack(state, target - choices[i], choices, i 1, res) # 回退撤销选择恢复到之前的状态 state.pop() def subset_sum_ii(nums: list[int], target: int) - list[list[int]]: 求解子集和 II state [] # 状态子集 nums.sort() # 对 nums 进行排序 start 0 # 遍历起始点 res [] # 结果列表子集列表 backtrack(state, target, nums, start, res) return res Driver Code if __name__ __main__: nums [4, 4, 5] target 9 res subset_sum_ii(nums, target) print(f输入数组 nums {nums}, target {target}) print(f所有和等于 {target} 的子集 res {res})代码中有三处设计细节值得展开用target本身充当剩余和函数签名里没有total变量每次选择后传入target - choices[i]当target 0即命中解。这是子集和 I 就引入的简化省去了一个显式的元素和累加器res.append(list(state))的拷贝state是全程共享的可变列表记录解时必须存入副本否则后续pop会破坏已记录的解i 1与i的差异这是子集和 II 相对子集和 I 最本质的改动。对照 subset_sum_i 的 Python 实现其递归调用传的是i元素可复用而本题传i 1从机制上杜绝了同一索引元素被二次选取。运行验证与回溯过程Driver Code 使用的测试输入为nums [4, 4, 5]、target 9实际运行结果输入数组 nums [4, 4, 5], target 9 所有和等于 9 的子集 res [[4, 5]]尽管数组里有两个4结果中只出现一条[4, 5]证明剪枝四生效第一轮遍历到第二个4时i start且choices[i] choices[i - 1]成立该分支被continue跳过。图解文档 给出了该输入下的完整回溯树四种剪枝在树中的落点一目了然结合上图可以验证各剪枝的分工剪枝一越界剪枝例如已选4后剩余5再选5恰好命中解但若剩余和为4选完5就为负本轮后续更大元素也无意义整轮直接终止剪枝二顺序去重由于每轮只从start向右选[4, 5]与[5, 4]这类换位子集永远不会同时产生——这正是子集和 I 中“选择序列下标必须非递减”约束的执行方式剪枝三不重复选元素选中索引i后下一轮起点为i 1索引i对应的元素在当前路径上不可能再出现剪枝四同层去重只在“同一轮内”比较相邻相等元素且受i start保护——当i start时该元素是本层的第一个候选必须保留否则所有等于该值的分支都被误剪。这里要特别辨析剪枝二与剪枝四的边界剪枝二消除的是不同下标顺序造成的重复如先 4 后 5 与先 5 后 4剪枝四消除的是同一层内相等值造成的重复如两个 4 在同层分别当分支根。二者缺一不可去掉剪枝四会输出[4, 5]两次把剪枝二改为从 0 开始遍历则会输出[5, 4]。与子集和 I 的代码级对比将子集和 II 与其前身 subset_sum_i.py 逐行对比差异恰好只有两处这也是理解本题约束如何落入代码的捷径# 子集和 I元素可重复选取 backtrack(state, target - choices[i], choices, i, res) # 子集和 II每个元素只可选一次 backtrack(state, target - choices[i], choices, i 1, res)以及子集和 II 新增的同层去重分支# 剪枝四如果该元素与左边元素相等说明该搜索分支重复直接跳过 if i start and choices[i] choices[i - 1]: continue除这两点外两者的框架完全一致入口排序 → 维护state与res→ 循环内越界剪枝 → 尝试 / 递归 / 回退的经典三段式。掌握了子集和 I 的读者只需理解“i变i 1”和“加一条相邻相等跳过”即可迁移到子集和 II。Python Tutor 可视化文件的使用方式codes/pythontutor/chapter_backtracking/目录为回溯源图每个核心算法都准备了一份单步可视化源文件如 subset_sum_i.md、subset_sum_i_naive.md、permutations_ii.md 等其文件形态是统一的头部注释声明对应源文件随后以!-- [file]{...}-[func]{...} --标记绑定关系正文则是一段 URL 编码的 Python 脚本。以子集和 II 为例该文件编码的脚本与 codes/python/chapter_backtracking/subset_sum_ii.py 完全相同额外携带了一个指向 Python Tutor 在线渲染页面的链接打开后可单步观察backtrack的调用栈、state列表随append/pop的伸缩过程以及每次剪枝触发时循环变量的取值是调试回溯逻辑的高效手段。多语言参考实现同一套算法在仓库中提供了十余种语言的对照实现核心结构排序 四重剪枝 i 1递归保持一致可横向比对Python、Java、C、C、C#、Go、JavaScript、TypeScript、Rust、Swift、Kotlin、Ruby、Dart从源码结构看各版本对剪枝一的实现存在break与continue两种变体C 版为continue正确性不受影响但break变体在元素较多时循环开销更小。小结子集和 II 是回溯源图中“去重”技巧的集大成者可视化源文件 内嵌的代码用不到 30 行就演示了完整的组合去重范式排序是一切的前提使相等元素相邻、越界判断可以breakstart游标 i 1递归同时承担了“子集无序”和“元素不重复选取”两个约束i start and choices[i] choices[i - 1]是处理重复元素的标准同层去重写法i start这个边界条件不可省略越界剪枝让搜索树在target较大时显著缩小与去重剪枝叠加后才是该算法实际可用的原因。这套“排序 游标 同层去重”的模板同样适用于其他含重复元素的组合类问题如带重复元素的组合总和建议读者对照 回溯源图 与 子集和问题图解 进一步练习手工推演回溯树。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考