python - 整数的所有排列都对应于特定的和

Question

我想从整数列表[3,5,7,9]生成所有排列，这会产生特定的总和值15。我实现了这个，没问题。

def add_next(seq, count, m):
    s = sum(seq)
    if s == m:
        count += 1
        print(seq)
    elif s < m:
        for i in [3,5,7,9]:
            add_next(seq + [i], count, m)
    else:
        return count

add_next([], 0, 15)

输出:

[3, 3, 3, 3, 3]
[3, 3, 9]
[3, 5, 7]
[3, 7, 5]
[3, 9, 3]
[5, 3, 7]
[5, 5, 5]
[5, 7, 3]
[7, 3, 5]
[7, 5, 3]
[9, 3, 3]

问题是如何重写此函数以仅返回可能的排列数作为函数结果？由于对于巨大的列表和大的总和值，生成所有字符串输出是不合理的。我不完全理解如何在递归函数内部和外部传递值。

我尝试过:

def add_next2(seq, count, m):
    s = sum(seq)
    if s == m:
        count += 1
        print(seq)
    elif s < m:
        for i in [3,5,7,9]:
            count = add_next2(seq + [i], count, m)
    else:
        return count

add_next([], 0, 15)

但它返回错误TypeError: unsupported operand type(s) for +=: 'NoneType' and 'int'。所以count是None。为什么？

另一种选择是如何重写此函数以将其转换为生成器并依次生成输出字符串？

Answer 1

如果您只是计算成功的递归结果，则不需要“count”作为参数。您可以将成功的结果返回为 1，将不成功的结果返回为 0，让它们累加。

编辑2更简洁但仍然可读

def add_next(seq, m):
    s = sum(seq)
    count = 1 if s == m else 0
    if s < m:
        for i in [f for f in [3,5,7,9] if s + f <= m]:
            count += add_next(seq + [i], m)
    return count

print(add_next([], 15))

编辑您还可以过滤您的 [3,5,7,9] 列表，以便您的 for i in 循环仅处理有可能成功的元素。

for i in [f for f in [3,5,7,9] if s + f <= m]: