为什么我的用于生成约束子集的Python递归函数无法排除无效组合？

Question

我正在尝试编写一个Python函数来生成数字列表的所有组合，但有特定的约束。这就是我想要实现的目标：

1. 生成列表的所有可能子集。
2. 确保每个子集的总和不超过给定的目标值（max_sum）。 例如，如果我的输入是numbers = [2, 3, 5]并且max_sum = 6，我希望输出为： [[]、[2]、[3]、[5]、[2、3]] 这是我迄今为止尝试过的：

def generate_combinations(nums, max_sum, current=[], index=0):
    if sum(current) > max_sum:
        return []
    if index == len(nums):
        return [current]
    include = generate_combinations(nums, max_sum, current + [nums[index]], index + 1)
    exclude = generate_combinations(nums, max_sum, current, index + 1)
    return include + exclude


numbers = [2, 3, 5]
max_sum = 6
result = generate_combinations(numbers, max_sum)
print(result)

但是，这会返回如下结果：

[[2], [2, 3], [2, 3, 5], [3], [3, 5], [5]]

问题：

1. 某些子集超过 max_sum（例如 [2, 3, 5]）。
2. 我希望包含空子集 []，但它丢失了。

我尝试过的：

添加一个条件以在递归开始时显式包含 []，但这并没有按预期工作。 打印调试语句来检查中间值，但我不确定过滤逻辑在哪里中断。

我的基于 max_sum 过滤子集的递归逻辑有什么问题？ 有没有更好的方法来构造递归以满足要求？ 在生成约束组合时是否应该考虑任何边缘情况？

Answer 1

据我所知，你不需要递归。你想要的可以通过这样的生成器来实现：

import itertools

def generate_combinations(*nums, max_sum=None):
    # for all lengths from 0 to the full length of "nums"
    for k in range(len(nums)):
        # let itertools generate the combinations:
        for subset in itertools.combinations(nums, k):
            # apply conditional "max_sum" limit (if provided):
            if max_sum is None or sum(subset)<=max_sum:
                # yield next subset as a list
                yield list(subset)

>>> list(generate_combinations(2,3,5, max_sum=6))
[[], [2], [3], [5], [2, 3]]