《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的组合且结果中不允许出现重复组合变体输入数组约束元素选取规则对应实现文件Python子集和问题 I无重复元素每个元素可不限制次数地选用subset_sum_i.py子集和问题 II可能含重复元素每个元素只允许选取一次subset_sum_ii.py两个约束差异看似很小却直接决定了剪枝策略的不同变体 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 轮和第 2 轮分别选择3和4则所有包含这两个元素的子集都被生成完毕可记为[3, 4, …]此后若第 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 第 838 行对照驱动代码可以看到输入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 第 842 行其中等值剪枝的条件i start and choices[i] choices[i - 1]值得细看i start限定了同一轮内的比较范围——若i start说明当前元素是本轮第一个候选其左侧元素属于更早的轮次不构成同轮重复必须保留。输入nums [4, 4, 5]、target 9时输出为[[4, 5]]两个值为 4 的元素不再产生重复分支。从源码结构看变体 II 共包含四种剪枝汇总如下剪枝代码位置作用剪枝 1target - choices[i] 0时breaksubset_sum_ii.py数组已排序后续元素更大超出部分必然越界直接终止本轮循环剪枝 2for i in range(start, ...)subset_sum_ii.py保证选择下标非降消除顺序不同产生的重复子集剪枝 3下一轮从i 1开始subset_sum_ii.py满足每个元素只选一次的约束剪枝 4i start and choices[i] choices[i-1]时continuesubset_sum_ii.py同一轮内跳过与左邻相等的元素消除等值重复多语言实现与验证方式《Hello 算法》仓库为子集和问题的三个版本naive / I / II提供了统一命名的多语言实现便于对照阅读Pythonru/codes/python/chapter_backtracking/subset_sum_i.py、subset_sum_i_naive.py、subset_sum_ii.pyJavaru/codes/java/chapter_backtracking/subset_sum_i.java、subset_sum_ii.javaGoru/codes/go/chapter_backtracking/subset_sum_ii.goRustru/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]target9)的行为差异在 Go 环境下执行go test即可复现验证。Python 侧也可用 ru/codes/python/test_all.py 批量运行各章节脚本确认所有示例代码可正常执行。小结本文沿《Hello 算法》「回溯算法」一章的脉络完整还原了子集和问题的求解过程初始解法复用排列问题的试错 回退框架去掉selected状态即可获得朴素回溯但其区分选择顺序会输出[4, 5]、[5, 4]这类重复子集变体 I用start变量强制选择下标非降i_1 ≤ i_2 ≤ … ≤ i_m配合排序后越界即break与扣减target代替求和变量实现每个子集仅生成一次变体 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
《Hello 算法》回溯算法实战：子集和问题中的位置剪枝与等值元素去重
《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的组合且结果中不允许出现重复组合变体输入数组约束元素选取规则对应实现文件Python子集和问题 I无重复元素每个元素可不限制次数地选用subset_sum_i.py子集和问题 II可能含重复元素每个元素只允许选取一次subset_sum_ii.py两个约束差异看似很小却直接决定了剪枝策略的不同变体 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 轮和第 2 轮分别选择3和4则所有包含这两个元素的子集都被生成完毕可记为[3, 4, …]此后若第 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 第 838 行对照驱动代码可以看到输入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 第 842 行其中等值剪枝的条件i start and choices[i] choices[i - 1]值得细看i start限定了同一轮内的比较范围——若i start说明当前元素是本轮第一个候选其左侧元素属于更早的轮次不构成同轮重复必须保留。输入nums [4, 4, 5]、target 9时输出为[[4, 5]]两个值为 4 的元素不再产生重复分支。从源码结构看变体 II 共包含四种剪枝汇总如下剪枝代码位置作用剪枝 1target - choices[i] 0时breaksubset_sum_ii.py数组已排序后续元素更大超出部分必然越界直接终止本轮循环剪枝 2for i in range(start, ...)subset_sum_ii.py保证选择下标非降消除顺序不同产生的重复子集剪枝 3下一轮从i 1开始subset_sum_ii.py满足每个元素只选一次的约束剪枝 4i start and choices[i] choices[i-1]时continuesubset_sum_ii.py同一轮内跳过与左邻相等的元素消除等值重复多语言实现与验证方式《Hello 算法》仓库为子集和问题的三个版本naive / I / II提供了统一命名的多语言实现便于对照阅读Pythonru/codes/python/chapter_backtracking/subset_sum_i.py、subset_sum_i_naive.py、subset_sum_ii.pyJavaru/codes/java/chapter_backtracking/subset_sum_i.java、subset_sum_ii.javaGoru/codes/go/chapter_backtracking/subset_sum_ii.goRustru/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]target9)的行为差异在 Go 环境下执行go test即可复现验证。Python 侧也可用 ru/codes/python/test_all.py 批量运行各章节脚本确认所有示例代码可正常执行。小结本文沿《Hello 算法》「回溯算法」一章的脉络完整还原了子集和问题的求解过程初始解法复用排列问题的试错 回退框架去掉selected状态即可获得朴素回溯但其区分选择顺序会输出[4, 5]、[5, 4]这类重复子集变体 I用start变量强制选择下标非降i_1 ≤ i_2 ≤ … ≤ i_m配合排序后越界即break与扣减target代替求和变量实现每个子集仅生成一次变体 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考