和がkとなるようなn個の非負整数の順列を重複なく全列挙する方法が知りたいです.
ナイーブに実装しましたがO(k^n)
,これより計算量が改善される解法は存在しますか.
# Python 3.10.5
from itertools import product
def sol(n, k):
for perm in product(range(k+1), repeat=n):
if sum(perm) == k:
yield perm
print(*sol(n=2, k=4))
# (0, 4) (1, 3) (2, 2) (3, 1) (4, 0)
print(*sol(n=3, k=3))
# (0, 0, 3) (0, 1, 2) (0, 2, 1) (0, 3, 0) (1, 0, 2) (1, 1, 1) (1, 2, 0) (2, 0, 1) (2, 1, 0) (3, 0, 0)