企业官网建设流程全解析

《Hello 算法》回溯算法实战：子集和问题中的位置剪枝与等值元素去重

【免费下载链接】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 算法》仓库中「回溯算法」一章的子集和问题文档展开，系统讲解两个经典变体——"元素可无限重用"与"元素含重复且仅可选一次"——的完整求解思路：如何从排列问题迁移出初始解法、为什么事后去重不可行、如何用start位置剪枝保证每个子集只生成一次，以及如何用一条等值判断同时解决重复元素问题。读完本文，你将掌握回溯法中"试错 + 回退 + 剪枝"三要素在组合类搜索问题中的标准落地范式，并能在 ru/codes/python/chapter_backtracking/ 目录下找到可一键运行的多语言参考实现（Python、Java、C++、Go、Rust、C 等十余种语言）。

问题定义：两个变体的关键差异

《Hello 算法》在子集和问题（subset sum）中给出了两个层次递进的变体，二者的输入均为"正整数数组nums与正整数target"，目标是找出所有元素之和等于target的组合，且结果中不允许出现重复组合：

两个约束差异看似很小，却直接决定了剪枝策略的不同：变体 I 需要剪掉"不同顺序选择同一批元素"产生的重复分支；变体 II 则在此基础上还要剪掉"同一轮里选中两个相同值"产生的重复分支。

起点：从排列问题迁移出的初始解法

与排列问题一样，构建子集的过程可以被看作一连串"选择"的结果，每选择一次就动态更新"当前子集的元素和"，当和等于target时把对应子集记入结果列表。但有一个关键区别：排列问题中每个元素只能用一次，需要布尔列表selected记录选取状态；而在子集和问题 I 中元素可以无限重用，因此不再需要selected。对排列问题的代码稍作修改，就得到了初始版本：

def backtrack( state: list[int], target: int, total: int, choices: list[int], res: list[list[int]], ): """回溯算法：子集和 I""" # 如果子集元素之和为 target，则记录解 if total == target: res.append(list(state)) return # 遍历所有选择 for i in range(len(choices)): # 剪枝：若子集元素之和超过 target，则跳过此选择 if total + choices[i] > target: continue # 尝试：做选择，更新元素和 total state.append(choices[i]) # 进入下一轮选择 backtrack(state, target, total + choices[i], choices, res) # 回退：撤销选择，恢复到之前的状态 state.pop() def subset_sum_i_naive(nums: list[int], target: int) -> list[list[int]]: """求解子集和问题 I（存在重复子集）""" state = [] # 状态（子集） total = 0 # 子集元素之和 res = [] # 结果列表（子集列表） backtrack(state, target, total, nums, res) return res

（摘自 ru/codes/python/chapter_backtracking/subset_sum_i_naive.py）

以上述代码为例，输入数组[3, 4, 5]、目标值9，输出结果为[3, 3, 3]、[4, 5]、[5, 4]。虽然所有和为 9 的子集都被成功找到了，但其中出现了重复的[4, 5]与[5, 4]。原因很简单：搜索过程区分了元素的选取顺序，而子集本身不区分顺序——"先选 4 再选 5"与"先选 5 再选 4"是搜索树上两条不同的分支，却对应同一个子集。

为什么不在结果列表里事后去重？

最直接的想法是把去重放在最后，对结果列表做去重处理。但文档指出这个方案有两条硬伤：

• 当数组元素较多、尤其是target较大时，搜索过程会产生海量的重复子集，先去重意味着先承担巨大的生成开销；
• 比较两个子集（即两个数组）本身代价不低：需要先对数组排序，再逐元素比较。

因此更优的思路是在搜索过程中直接剪掉重复分支，让每个子集从一开始就只被生成一次。

变体 I 的剪枝原则：选择下标必须非降

观察重复子集的产生规律：它们都源于数组元素被以不同的顺序选取。比如：

1. 若第 1 轮和第 2 轮分别选择3和4，则所有包含这两个元素的子集都被生成完毕，可记为[3, 4, …]；
2. 此后若第 1 轮选择4，第 2 轮就必须跳过3，因为[4, 3, …]与第 1 条已经生成的子集完全重复。

搜索过程中每一层的候选是从左到右依次尝试的，所以越靠右的分支会剪掉越多左侧分支。同理，第 1 轮选5后，第 2 轮的3和4都要跳过，因为[5, 3, …]、[5, 4, …]与前两种情况完全重复。

把它写成一般性结论：若输入数组为 $[x_1, x_2, \dots, x_n]$，一次搜索得到的选择序列为 $[x_{i_1}, x_{i_2}, \dots, x_{i_m}]$，那么它必须满足 $i_1 \leq i_2 \leq \dots \leq i_m$。所有不满足该条件的选择序列都会产生重复，应当被剪枝。

变体 I 的最终代码：start指针 + 排序剪枝

实现上述剪枝只需一个start变量，表示本轮搜索的起始位置。选定元素 $x_i$ 后，下一轮从下标i开始（而不是i + 1，因为变体 I 允许重复选取同一元素），这样选择序列天然满足下标非降，每个子集只会被构造一次。

文档同时给出另外两处优化：

• 先对nums排序。数组有序后，一旦当前子集的和超过target，由于后续元素只会更大，可以直接break跳出整个循环，而不只是continue跳过当前元素；
• 用"从target中不断扣减"替代单独的求和变量total。当target被扣到 0 时，即找到一个解，代码更简洁。

def backtrack( state: list[int], target: int, choices: list[int], start: int, res: list[list[int]] ): """回溯算法：子集和 I""" # 如果子集元素之和为 target，则记录解 if target == 0: res.append(list(state)) return # 遍历所有选择 # 剪枝2：从 start 开始遍历，以避免生成重复子集 for i in range(start, len(choices)): # 剪枝1：若子集元素之和超过 target，则立即结束循环 # 由于数组已排序，后续元素更大，子集元素之和必然超过 target if target - choices[i] < 0: break # 尝试：做选择，更新 target 和 start state.append(choices[i]) # 进入下一轮选择 backtrack(state, target - choices[i], choices, i, res) # 回退：撤销选择，恢复到之前的状态 state.pop() def subset_sum_i(nums: list[int], target: int) -> list[list[int]]: """求解子集和问题 I""" state = [] # 状态（子集） nums.sort() # 对 nums 排序 start = 0 # 遍历的起始节点 res = [] # 结果列表（子集列表） backtrack(state, target, nums, start, res) return res

（摘自 ru/codes/python/chapter_backtracking/subset_sum_i.py 第 8～38 行）

对照驱动代码可以看到，输入nums = [3, 4, 5]、target = 9时，该函数输出[[3, 3, 3], [4, 5]]，重复项[5, 4]已被彻底消除。

变体 II：处理重复元素的"等值剪枝"

变体 II 的输入数组可能包含重复元素，且每个元素只允许选取一次。例如数组[4, 4, 5]、目标值9，直接沿用变体 I 的代码会输出[4, 5]和[4, 5]两条重复结果。

重复产生的根源是：相等的元素在同一轮搜索中被选中了多次。由于排序后等值元素必然相邻，解法非常自然：若当前轮中的当前元素与其左侧相邻元素相等，说明这一选择分支在上一轮已经考察过了，跳过当前元素即可。

文档指出，"每个元素只能选一次"这一约束也可以借start一并实现：选定元素 $x_i$ 后，下一轮从下标i + 1开始（与变体 I 的i形成关键区别）。一个变量同时完成了"去重"和"禁止重选"两件事。

变体 II 的最终代码：四重剪枝

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 # 遍历所有选择 # 剪枝2：从 start 开始遍历，以避免生成重复子集 # 剪枝3：从 start 开始遍历，以避免重复选取同一元素 for i in range(start, len(choices)): # 剪枝1：若子集元素之和超过 target，则立即结束循环 # 由于数组已排序，后续元素更大，子集元素之和必然超过 target if target - choices[i] < 0: break # 剪枝4：若该元素与左侧元素相等，则搜索分支重复，立即跳过 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

（摘自 ru/codes/python/chapter_backtracking/subset_sum_ii.py 第 8～42 行）

其中等值剪枝的条件i > start and choices[i] == choices[i - 1]值得细看：i > start限定了"同一轮内"的比较范围——若i == start，说明当前元素是本轮第一个候选，其左侧元素属于更早的轮次，不构成同轮重复，必须保留。输入nums = [4, 4, 5]、target = 9时，输出为[[4, 5]]，两个值为 4 的元素不再产生重复分支。

从源码结构看，变体 II 共包含四种剪枝，汇总如下：

多语言实现与验证方式

《Hello 算法》仓库为子集和问题的三个版本（naive / I / II）提供了统一命名的多语言实现，便于对照阅读：

• Python：ru/codes/python/chapter_backtracking/subset_sum_i.py、subset_sum_i_naive.py、subset_sum_ii.py
• Java：ru/codes/java/chapter_backtracking/subset_sum_i.java、subset_sum_ii.java
• Go：ru/codes/go/chapter_backtracking/subset_sum_ii.go
• Rust：ru/codes/rust/chapter_backtracking/subset_sum_ii.rs
• 此外还有 C、C++、C#、JavaScript、TypeScript、Swift、Ruby、Kotlin、Dart 等语言版本，均位于 ru/codes/ 对应的chapter_backtracking目录中

每个 Python 文件底部都带有__main__驱动代码，直接运行即可看到输出，例如：

python ru/codes/python/chapter_backtracking/subset_sum_ii.py # 输入数组 nums = [4, 4, 5], target = 9 # 所有元素之和为 9 的子集：res = [[4, 5]]

Go 语言则通过标准testing包提供自动化用例，ru/codes/go/chapter_backtracking/subset_sum_test.go 中定义了TestSubsetSumINaive、TestSubsetSumI、TestSubsetSumII三个测试函数，分别验证朴素版（含重复输出）、剪枝后的变体 I 与变体 II 对同一组输入([3,4,5] / [4,4,5]，target=9)的行为差异，在 Go 环境下执行go test即可复现验证。Python 侧也可用 ru/codes/python/test_all.py 批量运行各章节脚本，确认所有示例代码可正常执行。

小结

本文沿《Hello 算法》「回溯算法」一章的脉络，完整还原了子集和问题的求解过程：

1. 初始解法：复用排列问题的"试错 + 回退"框架，去掉selected状态即可获得朴素回溯，但其区分选择顺序，会输出[4, 5]、[5, 4]这类重复子集；
2. 变体 I：用start变量强制选择下标非降（i_1 ≤ i_2 ≤ … ≤ i_m），配合"排序后越界即break"与"扣减target代替求和变量"，实现每个子集仅生成一次；
3. 变体 II：在变体 I 基础上新增"同轮等值跳过"剪枝，并把下一轮起点从i改为i + 1，用一个start指针同时解决等值重复与元素禁选两次两个问题，共形成四重剪枝。

这套"以状态变量约束搜索空间 + 以排序性质提前终止"的剪枝思想，是该仓库中八皇后、子序列、字符串解码等回溯问题的通用范式，可参考同章的 ru/docs/chapter_backtracking/backtracking_algorithm.md 了解回溯算法的完整理论背景。

【免费下载链接】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