Hello 算法：子集和问题的回溯剪枝详解——从重复子集成因到四种剪枝策略

本文基于《Hello 算法》回溯源中的「子集和问题」章节（subset_sum_problem.md），系统讲解无重复元素与含重复元素两种子集和问题的回溯求解方法。读完本文，你将理解「为什么朴素回溯会产出重复子集」，并掌握 start 遍历起点控制、排序后越界剪枝、减法消去统计、相等元素剪枝这四种核心剪枝技巧，可直接复用于 LeetCode「组合总和」「组合总和 II」一类问题。

问题定义：两种子集和变体

子集和 I：元素可无限次选取

给定一个正整数数组 nums 和一个目标正整数 target，请找出所有可能的组合，使得组合中的元素和等于 target。约束条件为：

• 数组无重复元素；
• 每个元素可以被选取多次；
• 结果列表不应包含重复组合。

例如，输入集合 {3, 4, 5} 和目标整数 9，解为 {3, 3, 3} 和 {4, 5}。这里「子集」不区分元素顺序，即 {4, 5} 和 {5, 4} 是同一个子集。

子集和 II：含重复元素，每个元素只能选一次

给定一个正整数数组 nums 和一个目标正整数 target，要求同上，但约束变为：

• 输入数组可能包含重复元素；
• 每个元素只可被选择一次。

例如数组 [4, 4, 5] 与目标 9：两个 4 虽然数值相同，但它们是数组中两个不同的位置，每个都只能被选一次。

这两个变体分别对应了「可重复选取」与「元素含重复」这两类经典分支去重场景，下面的解法演进过程正是从 I 逐步推导到 II 的。

参考全排列解法：朴素回溯与重复子集

从全排列迁移到子集和

类似于 全排列问题 的解法，我们可以把子集的生成过程想象成一系列选择的结果，并在选择过程中实时更新「元素和」，当元素和等于 target 时，就将子集记录至结果列表。

而与全排列问题不同的是，本题集合中的元素可以被无限次选取，因此无须借助 selected 布尔列表来记录元素是否已被选择（对比 permutations_ii.py 中全排列 II 必须维护 selected 状态）。只需将全排列中「选过的不能选」的遍历限制放宽为「每个选择都可以再次选」，即可得到朴素解法。

朴素实现代码

以下为仓库中 subset_sum_i_naive.py 的完整实现：

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

代码中每个回溯层都从索引 0 开始遍历所有选择，并允许下一层再次从头遍历——这正是「元素可无限次选取」的体现。

重复子集的成因

向以上代码输入数组 [3, 4, 5] 和目标元素 9，输出结果为 [3, 3, 3], [4, 5], [5, 4]。虽然成功找出了所有和为 9 的子集，但其中存在重复的子集 [4, 5] 和 [5, 4]。

原因可以从源码结构看出：搜索过程区分选择顺序。backtrack 函数在每一层都遍历全部 choices，先选 4 后选 5 与先选 5 后选 4 是搜索树上两条不同的分支，最终落到了同一个子集上。

若对结果列表进行事后去重，效率很低，有两方面原因：

• 当数组元素较多、尤其是 target 较大时，搜索过程会产生大量的重复子集；
• 比较子集（数组）的异同非常耗时，需要先排序数组，再逐个比较数组中每个元素的异同。

因此更好的方向是：在搜索过程中通过剪枝进行去重。

重复子集剪枝：用 start 控制选择序列单调

剪枝思路

观察重复分支的产生规律：重复子集是在以不同顺序选择数组元素时产生的。例如：

1. 当第一轮和第二轮分别选择 3 和 4 时，会生成包含这两个元素的所有子集，记为 [3, 4, ...]；
2. 之后，当第一轮选择 4 时，第二轮应该跳过 3，因为该选择产生的子集 [4, 3, ...] 和第 1 步中生成的子集完全重复。

在搜索过程中，每一层的选择都是从左到右被逐个尝试的，因此越靠右的分支被剪掉的越多：

1. 前两轮选择 3 和 5，生成子集 [3, 5, ...]；
2. 前两轮选择 4 和 5，生成子集 [4, 5, ...]；
3. 若第一轮选择 5，第二轮应该跳过 3 和 4，因为子集 [5, 3, ...] 和 [5, 4, ...] 与前两步中描述的子集完全重复。

总结来看，给定输入数组 [x1, x2, ..., xn]，设搜索过程中的选择序列为 [x_i1, x_i2, ..., x_im]，则该选择序列需要满足 i1 <= i2 <= ... <= im；不满足该非递减索引条件的选择序列都会造成重复，应当剪枝。

代码实现：start + 排序 + 减法消去

为实现该剪枝，我们初始化变量 start，用于指示遍历起始点。当做出选择 x_i 后，设定下一轮从索引 i 开始遍历（注意：传的是 i 而非 i + 1，因为本题允许同一元素重复选取，索引可以保持不严格递增）。这样做就可以让选择序列满足 i1 <= i2 <= ... <= im，从而保证子集唯一。

在此基础上，仓库代码还做了两项优化：

• 排序后越界剪枝：在开启搜索前先将数组 nums 排序。遍历所有选择时，当子集和超过 target 时直接结束循环（break），因为后面的元素更大，其子集和一定超过 target；
• 减法消去统计：省去元素和变量 total，通过在 target 上执行减法来统计元素和，当 target 等于 0 时记录解。

以下为 subset_sum_i.py 的完整实现，注释中的「剪枝一」「剪枝二」正是上述两种手段：

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

多语言实现可在仓库中对照查看：C++ 版本 subset_sum_i.cpp 用 sort(nums.begin(), nums.end()) 完成排序，递归签名与 Python 版一一对应；Go 版本及测试见 subset_sum_i.go、subset_sum_ii.go 与 subset_sum_test.go。所有语言版本的核心逻辑一致：start 从 i（可重复选）传递、排序后 break、target 减到 0 记录解。

含重复元素的情况：相等元素剪枝

新问题的成因

回到子集和 II 的设定：输入数组可能包含重复元素，每个元素只可被选择一次。直接套用子集和 I 的代码，给定数组 [4, 4, 5] 和目标元素 9，输出结果会变成 [4, 5], [4, 5]（分别对应第一个 4 和第二个 4），出现了重复子集。

造成这种重复的原因是相等元素在某轮中被多次选择：第一轮共有三个选择，其中两个都为 4，会产生两个重复的搜索分支，从而输出重复子集；同理，第二轮的两个 4 也会产生重复子集。

剪枝策略的叠加

为解决问题，我们需要限制相等元素在每一轮中只能被选择一次。实现方式比较巧妙：由于数组是已排序的，相等元素都是相邻的。这意味着在某轮选择中，若当前元素与其左边元素相等，则说明它已经被选择过，因此直接跳过当前元素：

# 剪枝四：如果该元素与左边元素相等，说明该搜索分支重复，直接跳过
if i > start and choices[i] == choices[i - 1]:
    continue

注意条件里的 i > start：当 i == start 时说明当前元素就是本轮第一个被选的元素，必须允许它被选，否则会把唯一合法分支也剪掉；只有 i > start 且与前驱相等时，才说明是「同一轮内的重复选择」。

与此同时，本题规定每个数组元素只能被选择一次。我们同样利用变量 start 来满足该约束：当做出选择 x_i 后，设定下一轮从索引 i + 1 开始向后遍历（注意与子集和 I 的传 i 不同）。这一改动一举两得：既去除了重复子集，也避免了重复选择同一元素。

代码实现

以下为 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

对照子集和 I，关键差异只有两处：递归传参由 i 变为 i + 1（元素只可选一次），以及新增的「相等元素剪枝」判断。

图中展示了数组 [4, 4, 5] 和目标元素 9 的完整回溯过程，共包含四种剪枝操作，可将图示与代码注释结合，逐一核对每种剪枝生效的位置。

小结：四类剪枝的适用场景

剪枝	手段	解决的问题	适用题目
剪枝一	排序后 target - choices[i] < 0 时 break	越界分支（子集和超过 target）	I、II
剪枝二	遍历从 start 开始，且选择 x_i 后下一轮传 i	选择顺序不同导致的重复子集	I（可重复选取）
剪枝三	选择 x_i 后下一轮传 i + 1	同一元素被重复选择	II（每元素选一次）
剪枝四	i > start 且 choices[i] == choices[i - 1] 时 continue	相等元素在同一轮被多次选择	II（数组含重复元素）

从实现细节看，两类题目共享同一套骨架：排序预处理、start 控制遍历范围、减法消去统计元素和；差异集中在「递归时传 i 还是 i + 1」以及是否需要相等元素剪枝。掌握这条演进路径后，面对「可重复选取 / 不可重复选取」「无重复元素 / 含重复元素」的任意组合，都可以按需装配对应的剪枝策略。