列表推导式求和问题：递归生成子列表后求各子列表和（支持n≥40）

一、修正代码：直接生成子集和而非嵌套列表 #

你的原代码生成的是子集元素的组合列表，要直接返回每个子集的和，需要调整递归的返回值类型：

• 初始条件改为返回[0]（空集的和为0）
• 递归时，对前n-1个元素的每个和，分别加上0或当前元素的值，生成新的和列表

修正后的代码：

a = [1,2,15]
def tt(n):
    if n < 1:
        return [0]  # 空集的和为0
    prev_sums = tt(n-1)
    current_num = a[n-1]
    # 遍历前n-1的所有和，分别生成加0和加当前元素的新和
    return [s + v * current_num for s in prev_sums for v in [0, 1]]

print(tt(3))

执行结果：[0, 15, 2, 17, 1, 16, 3, 18]（顺序与你期望的略有差异，但包含所有正确的子集和）

二、支持n=40及以上的优化方案 #

当n=40时，子集数量是2^40（约1万亿），直接生成所有和的列表会导致内存溢出，必须用集合去重+迭代累加的方式优化：

• 用集合存储当前所有子集和，自动去重（如果存在重复的和，能大幅减少存储量）
• 迭代遍历每个元素，将当前所有和加上该元素后，合并到原集合中

优化后的代码：

a = [1,2,15]
def tt(n):
    subset_sums = {0}
    for i in range(n):
        num = a[i]
        # 复制当前集合，避免遍历过程中修改集合导致的问题
        temp = subset_sums.copy()
        # 将每个现有和加上当前元素，加入集合
        for s in temp:
            subset_sums.add(s + num)
    # 可选：返回排序后的列表，保持结果有序
    return sorted(subset_sums)

print(tt(3))  # 输出 [0, 1, 2, 3, 15, 16, 17, 18]

优势： #

1. 内存占用大幅降低：如果存在重复的子集和，集合会自动去重，比如当a中有重复元素或线性组合元素时，存储量远小于2^n
2. 避免递归栈限制：迭代方式没有递归深度问题，即使n=100也能正常运行
3. 时间效率更高：时间复杂度为O(k*n)，其中k是当前集合的大小，远低于递归生成所有子集的O(2^n)

内容的提问来源于stack exchange，提问作者Victor Johnson