在Python中找到所有'n'个正数加起来等于'k'的所有组合？

Question

如何在Python中高效地找到n个正整数的所有可能组合加到给定数字k？

我知道我可以通过过滤所有可能的组合来解决此问题：

import itertools


def to_sum_k(n, k):
    for i in itertools.product(range(1, k - n + 2), repeat=n):
        if sum(i) == k:
            yield i


print(list(to_sum_k(3, 5)))
# [(1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 1, 2), (2, 2, 1), (3, 1, 1)]

---

[我已经看到类似的内容已经以抽象方式here进行了讨论，但是我看不到将其转换为代码的方式。

Answer 1

您对效率有何要求？我认为itertools已经优化，所以

from itertools import combinations_with_replacement as cwr

def to_sum(n, k):
    return list(filter(lambda x: sum(x) == k, cwr(range(1, k), n)))

to_sum(3, 5)

Out[1]: [(1, 1, 3), (1, 2, 2)]

Answer 2

这是一个递归解决方案：

def to_sum_k(n, k):
    if n == 1: 
        return [ [k] ]
    if n > k or n <= 0:
        return []
    res = []
    for i in range(k):
        sub_results = to_sum_k(n-1, k-i)
        for sub in sub_results:
            res.append(sub + [i])
    return res    

to_sum_k(3, 5)

结果：

[[5, 0, 0],
 [4, 1, 0],
 [3, 2, 0],
 [2, 3, 0],
 [1, 4, 0],
 [4, 0, 1],
 [3, 1, 1],
 [2, 2, 1],
 [1, 3, 1],
 [3, 0, 2],
 ...
 [2, 1, 2],