合計がXになる整数の組み合わせを出力する（重複あり）方法を教えてください。

Question

前提

以下のサイトで重複なしの合計がXになる整数の組み合わせを出力する方法が紹介されているのですが
同じ条件で重複を許す組み合わせも出力できるようにするにはどうすればよいのでしょうか。

「qiita:合計がXになる整数の組み合わせを出力する」
https://qiita.com/Cesaroshun/items/6302542e4e32602d775d

実現したいこと

リストは以下のリストで合計が10になる組み合わせ（重複あり）を出力したい
list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

重複なしのコード（上記HP参照）

list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

def get_integral_value_combination(list, target):
def a(idx, l, r, t):
if t == sum(l): r.append(l)
elif t < sum(l): return
for u in range(idx, len(list)):
a((u + 1), l + [list[u]], r, t)
return r
return a(0, [], [], target)

print get_integral_value_combination(list, 10)

Comments

[arcxor]

コードを示す場合は、「コードの挿入」（整形済みテキスト）を用いてください。

Answer 1

list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

def get_integral_value_combination(list, target):
    def a(idx, l, r, t):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(list)):
            a(u, l + [list[u]], r, t)
        return r
    return a(0, [], [], target)

print(get_integral_value_combination(list, 10))

[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 6], [1, 1, 1, 2, 2, 3], [1, 1, 1, 2, 5], [1, 1, 1, 3, 4], [1, 1, 1, 7], [1, 1, 2, 2, 2, 2], [1, 1, 2, 2, 4], [1, 1, 2, 3, 3], [1, 1, 2, 6], [1, 1, 3, 5], [1, 1, 4, 4], [1, 1, 8], [1, 2, 2, 2, 3], [1, 2, 2, 5], [1, 2, 3, 4], [1, 2, 7], [1, 3, 3, 3], [1, 3, 6], [1, 4, 5], [1, 9], [2, 2, 2, 2, 2], [2, 2, 2, 4], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5], [2, 4, 4], [2, 8], [3, 3, 4], [3, 7], [4, 6], [5, 5], [10]]

再帰呼び出しの第1引数を u + 1 から u に変更するだけです。

Comments

[poohchin]

ありがとうございました