Hello 算法子集和 I 回溯算法详解：剪枝去重原理与 Python 逐步可视化实战

本篇以《Hello 算法》仓库中的 Python Tutor 可视化文件 subset_sum_i.md 为核心，完整拆解"子集和 I"问题的回溯求解过程：如何用一个 start 参数消除重复子集、如何利用排序数组实现越界剪枝、如何用 target 减法替代累加器统计元素和。读完后你将能够读懂并复现仓库中 codes/python/chapter_backtracking/subset_sum_i.py 的完整实现，并理解该问题与朴素版本的差异所在。

这个可视化文件在仓库中的定位

Hello 算法仓库为每章的核心算法提供了"双轨"材料：

• 可运行的多语言源码，如 subset_sum_i.py；
• Python Tutor 可视化条目，统一存放在 codes/pythontutor/chapter_backtracking/ 目录下，每个 .md 文件本质上是一个指向 Python Tutor 在线解释器 render.html 渲染页的链接。

subset_sum_i.md 即属于后一类。它的正文只有一个渲染链接，链接的 code 查询参数中 URL 编码了子集和 I 的完整可运行 Python 代码（含逐行中文注释），同时携带若干执行状态参数。将链接中的代码解码后，它与仓库源码 subset_sum_i.py 完全同构，二者互为镜像。下面给出的代码即该链接内嵌代码的完整解码结果（对应 subset_sum_i.py 的 backtrack 与 subset_sum_i 两个函数）。

算法完整代码与参数说明

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
    # 遍历所有选择
    # 剪枝二：从 start 开始遍历，避免生成重复子集
    for i in range(start, len(choices)):
        # 剪枝一：若子集和超过 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


"""Driver Code"""
if __name__ == "__main__":
    nums = [3, 4, 5]
    target = 9
    res = subset_sum_i(nums, target)

    print(f"输入数组 nums = {nums}, target = {target}")
    print(f"所有和等于 {target} 的子集 res = {res}")

问题定义（引自配套文档 subset_sum_problem.md）：给定一个正整数数组 nums 和一个目标正整数 target，找出所有可能的组合，使得组合中的元素和等于 target。本题中数组无重复元素，且每个元素可以被无限次重复选取；子集不区分元素顺序，比如 [4, 5] 和 [5, 4] 是同一个子集。例如输入集合 {3, 4, 5} 和目标整数 9，解为 [3, 3, 3], [4, 5]。

backtrack 函数的 5 个参数各司其职：

参数	类型	含义
state	list[int]	当前已选元素构成的"状态"（当前子集）
target	int	剩余目标值：每次选入元素 x 后传入 target - x，减到 0 即为一个解
choices	list[int]	候选元素数组（已排序）
start	int	本轮遍历的起始索引，用于保证选择序列不产生重复子集
res	list[list[int]]	结果列表，收集所有满足条件的子集

回溯主流程逐段解读

终止条件：target == 0

代码用"在 target 上做减法"替代了显式的元素和累加器。初始 target 就是题目给定的目标和，每选入一个元素 choices[i]，递归传入 target - choices[i]；当 target 恰好减到 0 时，说明当前 state 就是一个合法解，执行 res.append(list(state)) 后返回。这里必须用 list(state) 拷贝一份再入列，因为 state 是全程共享的可变列表，后续 pop 会改变它。

剪枝一：排序后的越界提前终止

if target - choices[i] < 0:
    break

这一行的前提是主函数中执行过 nums.sort()。数组从小到大排序后，一旦 choices[i] 已经大到使 target 变成负数，其右侧所有元素只会更大，子集和必然超过 target，于是用 break 直接结束整轮循环，而不是仅仅跳过当前元素。

这一点也是与朴素版本的关键差异：朴素实现 subset_sum_i_naive.py 未排序，只能用 continue 逐个跳过；优化版排序后即可升级为更彻底的 break。

剪枝二：start 索引消除重复子集

for i in range(start, len(choices)):
    ...
    backtrack(state, target - choices[i], choices, i, res)

注意递归调用传入的是 i 而不是 i + 1——这正是本题"元素可无限次重复选取"的体现：选了 choices[i] 后，下一轮仍可从 i 开始继续选它自己。

而 start 参数解决的是另一类重复：选择顺序不同导致的重复子集。搜索过程若区分选择顺序，先选 4 后选 5 与先选 5 后选 4 会是两条不同分支，却对应同一个子集 {4, 5}。配套文档 subset_sum_problem.md 给出了形式化结论：给定输入数组 $[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$，不满足该条件的选择序列都会造成重复，应当剪枝。实现方式即"当做出选择 $x_i$ 后，设定下一轮从索引 $i$ 开始遍历"，从而保证索引序列单调不减、子集唯一。

对比可以看得更清楚：朴素版本 subset_sum_i_naive.py 每轮都从 range(len(choices)) 即索引 0 开始遍历，因此向数组 [3, 4, 5] 输入目标 9 时输出 [3, 3, 3], [4, 5], [5, 4]，多出重复子集 [5, 4]（其 Driver 代码末尾也明确提示"该方法输出的结果包含重复集合"）。优化版则只输出 [3, 3, 3], [4, 5]。文档同时指出，"对结果列表事后去重"的替代方案效率很低：元素多且 target 大时会产生海量重复子集，且比较子集异同本身需要先排序再逐元素对比，非常耗时。

尝试—递归—回退三段式

每一轮选择遵循经典回溯骨架：

1. 尝试：state.append(choices[i])，做出选择；
2. 递归：backtrack(state, target - choices[i], choices, i, res)，进入下一轮选择；
3. 回退：state.pop()，撤销选择，恢复现场，供本轮循环尝试下一个 choices[i]。

三者缺一不可：只尝试不回退，state 会不断"污染"后续分支。从源码结构看，整棵搜索树的每个节点都严格经历这三步，这也是用 Python Tutor 单步调试时最值得关注的一组状态变化。

主函数初始化与运行结果

subset_sum_i 主函数只做四件事：

1. state = []：初始化空子集状态；
2. nums.sort()：对输入数组排序，为剪枝一提供单调性前提；
3. start = 0：设定全局遍历起始点；
4. res = []：创建结果列表，调用 backtrack 后返回。

以 Driver 代码为例，输入 nums = [3, 4, 5]、target = 9，运行输出：

输入数组 nums = [3, 4, 5], target = 9
所有和等于 9 的子集 res = [[3, 3, 3], [4, 5]]

从递归调用结构可以推断，最坏情况下分支数随输入规模呈指数增长，因此该算法适用于中小规模输入；其加速完全来自两项剪枝，而非多项式级的复杂度改进。

如何用 Python Tutor 观察该算法的执行过程

subset_sum_i.md 中链接的渲染参数决定了可视化呈现方式，逐一对应如下：

URL 参数	取值	含义
code	URL 编码的完整源码	解释器中加载并逐步执行的代码
py	311	按 Python 3.11 语义执行（对应类型注解 list[int] 等写法）
curInstr	16	打开页面时定位到的指令位置，即从回溯主体开始观察
mode	display	以逐步展示模式渲染执行画面
cumulative	false	调用栈不采用累积展示，每步只显示当前栈帧
heapPrimitives	nevernest	堆对象默认不展开嵌套层级

建议的阅读路径：先用 Driver 代码（nums = [3, 4, 5]、target = 9）逐步单步，观察 state 列表在 append / pop 之间的伸缩、target 从 9 一路递减到 0 的过程，以及每次递归传回的 start 值如何限制了下一轮的遍历范围；当某轮 target - choices[i] < 0 触发 break 时，恰好能直观看到剪枝一截断了哪些分支。

小结与延伸

本节代码围绕三个设计点展开，均可在 subset_sum_i.py 中逐行对应：

• start 索引剪枝：保证选择序列索引单调不减，从生成源头消除顺序型重复子集；
• 排序 + break 越界剪枝：利用数组单调性一次性砍掉整段无效分支；
• target 减法：省去 total 累加变量，把"是否达标"转化为 target == 0 判断。

同目录下的 subset_sum_i_naive.md 与 subset_sum_i_naive.py 提供了未去重的朴素对照版本，适合做剪枝前后的行为对比；而 subset_sum_ii.md 及其对应源码 subset_sum_ii.py 则将问题推广到"数组可能含重复元素、每个元素只可选一次"的情形，在本文两个剪枝之外新增了"相等元素剪枝"与 start = i + 1 的遍历约束，完整问题定义与四种剪枝的图解可继续查阅 subset_sum_problem.md。多语言读者亦可到各语言的 chapter_backtracking 目录（如 codes/java/chapter_backtracking/）查看同一题名的对应实现。