《Hello 算法》子集和问题 II（含重复元素）：回溯搜索与四种剪枝的 PythonTutor 可视化逐行走查

2026-09-07 09:45:45作者：伍霜盼Ellen

导读：本文以《Hello 算法》俄文版回溯章节的可视化素材 subset_sum_ii.md 为核心，系统讲解「子集和 II」问题——即输入数组含重复元素、每个元素只能使用一次的带约束组合搜索。读完本文，你将理解无序子集为何会产生重复解、排序 + 剪枝如何同时消除「顺序重复」与「同值重复」，并能逐行读懂与逐帧追踪完整的回溯代码，亲自动手验证 nums = [4, 4, 5], target = 9 的唯一解 [[4, 5]]。

一、问题定义：在子集和 I 之上叠加两道约束

在进入可视化代码之前，先明确这道题与经典「子集和 I」的差异。参照俄文版教材 subset_sum_problem.md 的第二部分（Учет повторяющихся элементов），题目描述如下：

给定正整数数组 nums 与正整数 target，找出所有元素之和等于 target 的组合，并以列表返回。输入数组中可能包含重复元素，且每个元素只允许被选择一次，最终结果中不得出现重复组合。

与不带重复元素的子集和 I 相比，本题叠加了两条约束：

对比维度	子集和 I	子集和 II
输入元素	互不重复	可能重复
元素使用次数	可无限重复选择	每个元素最多选一次
结果去重要求	无序、无重复子集	无序、无重复子集

例如对输入数组 $[4, \hat{4}, 5]$ （4 与 \hat{4} 是两个值相等但物理上不同的元素）与 target = 9，若直接套用子集和 I 的解法，会同时返回 [4, 5] 与 [\hat{4}, 5] —— 两个值完全相同的子集，这正是需要解决的重复问题。

本可视化文件在书中的定位

该 pythontutor 文件是一段可直接单步执行的算法素材。文件头部注释中的标记 [file]{subset_sum_ii}-[class]{}-[func]{subset_sum_ii} 精确声明了它所对应的代码位置：文件 subset_sum_ii.py 中的模块级函数 subset_sum_ii（无类，函数级）。也就是说，这份可视化呈现的正是教材正文代码块中展示的那一段核心算法，参见 subset_sum_problem.md 中 [file]{subset_sum_ii}-[class]{}-[func]{subset_sum_ii} 的引用。

二、朴素回溯为什么会输出重复子集

同《Hello 算法》中回溯章节反复强调的观点一致：子集问题可以建模为「逐轮做选择」的搜索过程，而子集本身不区分顺序，这天然与「选择序列分先后」的搜索模型冲突。

在子集和 II 中，重复解有两个不同来源：

顺序重复（order duplication）：先选 4 再选 5 与先选 5 再选 4 是两条不同搜索分支，但对应同一个子集 {4, 5}；
同值重复（equal-element duplication）：数组中两个相等的 4 在同一轮中被分别尝试，产生 [4, 5] 与 [\hat{4}, 5] 两条值完全相同的分支。

针对第 2 点，俄文教材给出了直观解释：若在子集和 I 的代码上直接运行 [4, \hat{4}, 5]，第一轮存在两个取值都为 4 的选择，就会展开两条彼此重复的搜索分支（示意图见教材 subset_sum_ii_repeat.png）。

在结果列表层面事后去重虽然直观，但代价高昂：重复分支数量可能巨大，且数组比较本身需要排序加逐位比较。因此本题与教材的解法思路一致——把去重前移到搜索过程中，用剪枝从根源上阻断重复分支的产生。

三、完整代码与逐行解读

可视化文件中的 URL 参数内嵌了去掉注释的精简可执行代码。为便于阅读，下面给出与之一一对应的、带注释的规范实现（来源于仓库 subset_sum_ii.py）：

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

其中 backtrack 的五个参数语义如下：

参数	类型	含义
`state`	`list[int]`	当前已选元素构成的子集（搜索状态）
`target`	`int`	剩余需要凑齐的目标和，减为 `0` 时记录解
`choices`	`list[int]`	候选数组，即排序后的 `nums`
`start`	`int`	本轮循环的起始下标，限制后续只能从 `start` 起选
`res`	`list[list[int]]`	结果收集器，命中解时以 `list(state)` 拷贝入列

与子集和 I 的关键差异：`i + 1` 而非 `i`

对比同一目录下的 subset_sum_i.py，两者骨架几乎一致，唯一的关键差异在递归传参上：

子集和 I（元素可无限重复）递归调用 backtrack(..., i, res)，因此同一下标可以在后续轮次再次被选中；
子集和 II（每元素最多一次）递归调用 backtrack(..., i + 1, res)，强制下一轮从 i + 1 开始，从而在避免子集顺序重复（剪枝二）的同时，把同一元素重复使用的可能性一并排除（剪枝三）。

这个 i + 1 的差异点，正是可视化代码中 state.append(...) 之后递归行 backtrack(state, target - choices[i], choices, i + 1, res) 与子集和 I 的最大区别，值得在逐行追踪时重点观察。

四、四种剪枝策略逐个拆解

在子集和 II 的实现中共有四处剪枝，覆盖「超过目标」「顺序重复」「元素重用」「同值重复」四类情况：

编号	判定条件	动作	作用对象	前提
剪枝一	`target - choices[i] < 0`	`break` 直接结束循环	和超出 `target` 的整段分支	数组已升序排序
剪枝二	`for i in range(start, ...)`	从 `start` 起遍历	顺序不同的重复子集	—
剪枝三	递归传入 `i + 1`	下一轮从后一个下标开始	同一元素的重复使用	—
剪枝四	`i > start and choices[i] == choices[i - 1]`	`continue` 跳过当前元素	同轮中值相等的重复分支	排序使相等元素相邻

逐条展开说明：

剪枝一（超额终止，break）：由于入口处 nums.sort() 已保证数组升序，若当前元素已让剩余目标 target - choices[i] 变为负数，那么其右侧元素只会更大、同样必然超额，因此用 break 跳出本轮循环而非 continue。这是整段代码正确性依赖排序的关键所在。

剪枝二（消除顺序重复）：把每轮的可选项起点锁定在 start，使任意搜索路径上的下标序列天然满足 $i_1 \le i_2 \le \dots \le i_m$ 。子集 ${4, 5}$ 只会在“先取 4 下标、后取 5 下标”这一种下标顺序下被构造一次，不会出现“先取 5、再回头取 4”的镜像分支。

剪枝三（禁止复用元素）：i + 1 让每个物理元素在其被选中之后从候选集中消失，这是“每个元素至多选一次”约束的落实。同时它不会破坏剪枝二的下标单调性，两者由同一个 start 机制统一实现。

剪枝四（同值去重，continue）：排序之后相等的元素必然相邻。当本轮的 choices[i] 与左侧邻居 choices[i - 1] 相等且 i > start 时，说明取值相同的分支刚被完整搜索过，当前元素（同值的另一个副本）只会复制出一模一样的子集，故直接跳过。

需要辨析的是：只有当 i > start 时才剪枝，i == start（即本轮的第一个同值元素）仍会被保留为合法代表。例如 [4, 4, 5] 中若存在合法子集 [4, 4, ...]（需要同时取两个副本），它会在第一轮取第 1 个 4、第二轮 start = 1、i == start == 1 时正常取到第 2 个 4，并不会被误剪。

五、实例推演：`nums = [4, 4, 5]`，`target = 9`

可视化文件的 Driver Code 片段给出的测试用例正是：

nums = [4, 4, 5]
target = 9
res = subset_sum_ii(nums, target)

手动推演整棵搜索树（排序后 nums = [4, 4, 5]）：

第一轮，start = 0：
- i = 0，取第 1 个 4，target 变 5，递归进入第二轮 start = 1；
  - 第二轮 i = 1：取第 2 个 4（i == start，合法），target 变 1，第三轮取 5 时 1 - 5 < 0 触发剪枝一，break 返回；
  - 第二轮 i = 2：取 5，target 变 0，命中解，记录 [4, 5]；
- i = 1，取第 2 个 4，但 i = 1 > start = 0 且 choices[1] == choices[0]，触发剪枝四，continue 跳过；
- i = 2，取 5，target 变 4，后续元素只剩 5，4 - 5 < 0 触发剪枝一，break。

最终结果列表只含一个子集：[[4, 5]]。两个物理上不同的 4 副本只贡献了同一个值解，重复被彻底消除。该搜索的完整回溯树在教材中以图展示，参见 subset_sum_ii.png，可与上文逐条剪枝推理互相印证。

子集和 II 的完整回溯搜索过程（nums = [4,4,5], target = 9）

六、如何本地运行与验证

该可视化素材对应的完整可执行源码位于仓库中，可以本地复现文中推演结果：

运行（俄文版）：python3 ru/codes/python/chapter_backtracking/subset_sum_ii.py
运行（简体中文版，代码逻辑一致）：python3 codes/python/chapter_backtracking/subset_sum_ii.py

预期终端输出为：

Входной массив nums = [4, 4, 5], target = 9
Все подмножества с суммой 9: res = [[4, 5]]

（即“输入数组 nums = [4, 4, 5], target = 9；所有和为 9 的子集：res = [[4, 5]]”），与第五节的手工推演完全一致。若将该用例换成无重复输入的 nums = [3, 4, 5], target = 9，则可在 subset_sum_i.py（允许无限重复）与 subset_sum_i_naive.py（去重前的最朴素版本，会输出 [4, 5] 与 [5, 4] 两个顺序重复解）中对比观察问题逐层收紧的过程。

七、可视化机制解读与配套资源

subset_sum_ii.md 这类 pythontutor 素材文件的核心是一段预先编码的可视化会话链接：URL 中嵌入了解析后的完整 Python 代码（含 backtrack 定义、subset_sum_ii 入口以及 __main__ 驱动用例），并带有 py=311 之类的运行环境参数，表明这段代码在 Python 3.11 语义下执行。打开该文件即可获得一条可直接逐步（step-through）走查的交互式执行路径——它不再需要你手动粘贴代码，驱动代码、函数定义与初始指令指针都已就绪。

在仓库中，同名的中文对照资产位于 codes/pythontutor/chapter_backtracking/subset_sum_ii.md，其中保留了完整的中文注释（剪枝一 至 剪枝四 的说明），与俄文版无注释的精简 URL 版互为补充，非常适合对照阅读，理解每行代码对应的剪枝意图。