如何高效枚举列表L中元素和不超过常数S的所有子集

原有方案的缺陷 #

现有基于全幂集生成后过滤的方案如下：

for subset in powerset(L):
    if sum(subset) <= S:
        yield subset

该方案时间复杂度为O(2^n)，会先生成列表的所有子集再做过滤，无论子集是否合法都会被生成。当列表长度超过20、或者符合条件的子集占比极低时，会产生巨量无效计算，性能完全不可接受。

优化方案：回溯+预排序剪枝 #

核心逻辑是在子集生成的过程中提前终止不可能合法的分支，从根源上避免无效子集的生成：

1. 先将列表做升序排序：后续遍历过程中如果当前元素加入后总和超过S，后面所有更大的元素必然也会让总和超过S，可以直接终止当前层的遍历，无需逐个判断
2. 递归回溯生成子集：每次选中元素后实时计算当前总和，一旦超过阈值直接剪枝，不会继续生成该分支下的所有子集

实现代码 #

基础版本（生成器，内存友好） #

不需要一次性存储所有结果，适合处理合法子集数量较大的场景：

def generate_valid_subsets(L: list[int], S: int):
    # 升序排序为后续连续剪枝做准备
    L = sorted(L)
    def backtrack(start_idx: int, current_subset: list[int], current_sum: int):
        # 首先返回当前的合法子集
        yield current_subset.copy()
        for i in range(start_idx, len(L)):
            new_sum = current_sum + L[i]
            if new_sum > S:
                # 后续元素比当前元素更大，加入后必然超过阈值，直接终止循环
                break
            current_subset.append(L[i])
            yield from backtrack(i + 1, current_subset, new_sum)
            # 回溯，撤销选择当前元素
            current_subset.pop()
    yield from backtrack(0, [], 0)

去重版本（适合存在重复元素的列表） #

如果原列表有重复数值，可添加同层重复元素跳过逻辑，避免生成内容完全相同的合法子集，进一步减少冗余：

def generate_unique_valid_subsets(L: list[int], S: int):
    L = sorted(L)
    def backtrack(start_idx: int, current_subset: list[int], current_sum: int):
        yield current_subset.copy()
        for i in range(start_idx, len(L)):
            # 跳过同层的重复元素，避免生成重复子集
            if i > start_idx and L[i] == L[i-1]:
                continue
            new_sum = current_sum + L[i]
            if new_sum > S:
                break
            current_subset.append(L[i])
            yield from backtrack(i + 1, current_subset, new_sum)
            current_subset.pop()
    yield from backtrack(0, [], 0)

性能提升效果 #

假设列表长度为20、S仅为列表总和的10%，原有全幂集方案需要遍历104万个子集，而剪枝后的方案仅需要遍历数千个合法子集，性能提升可达数百倍；如果S更小，性能提升会更明显。

内容的提问来源于stack exchange，提问作者Erel Segal-Halevi