Python: リストを組み合わせて合計がXになる整数の組み合わせの計算

ある特定の需要から、必要な消耗品リストの金額を組み合わせて、合計額がX円になる消耗品の組み合わせ(予算X円の残額を0円にする組み合わせ)を調べたくなった。

qiita.com

上記の再帰をうまく使ったコードほぼそのままだが、予約語の置き換えとPython3への対応を含め若干書き直したコードを紹介しておく。

items = [468, 183, 396, 550, 174, 209, 308, 325, 264, 209, 445, 272, 337, 334, 614, 134, 402, 141, 213, 243, 323, 646, 854]

def get_integral_value_combination(items, 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(items)):
            a((u + 1), l + [items[u]], r, t)
        return r
    return a(0, [], [], target)

result = get_integral_value_combination(items, 854)
for res in result:
    print(res)

出力は

[183, 396, 134, 141]
[183, 337, 334]
[174, 209, 337, 134]
[174, 209, 337, 134]
[209, 308, 337]
[209, 402, 243]
[308, 209, 337]
[264, 134, 213, 243]
[209, 402, 243]
[854]

おかげさまで、無事完了しました。