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

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

EDIT 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]: