《Hello 算法》子集和 II：Python 回溯解法与四重剪枝策略详解

2026-09-06 23:08:11作者：申梦珏Efrain

本篇以《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 单步执行的脚本（文件头部以  标注了所对应的源文件与函数）。这段代码与仓库中的 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 等），其文件形态是统一的：头部注释声明对应源文件，随后以  标记绑定关系，正文则是一段 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 行就演示了完整的组合去重范式：

排序是一切的前提，使相等元素相邻、越界判断可以 break；
start 游标 + i + 1 递归同时承担了“子集无序”和“元素不重复选取”两个约束；
i > start and choices[i] == choices[i - 1] 是处理重复元素的标准同层去重写法，i > start 这个边界条件不可省略；
越界剪枝让搜索树在 target 较大时显著缩小，与去重剪枝叠加后才是该算法实际可用的原因。