すべての部分集合和を求める（部分和問題）

Find all subset sum using dynamic programming – StackOverflow

「OPは動的計画法を用いてすべての組み合わせを用いる」だがDPでカウントは分かるけど，組み合わせを求める方法はよく分からない．簡単なのはDFSを用いる方法かなと．個人的に一番簡便かつ空間効率が許す限りに置いて効率的なのはnumpyで力づくの方法だけど．

import numpy as np


def count_dp(S, t):
    dp = [1] + [0]*t
    for i in S:
        for j in range(0, t-i+1):
            dp[i+j] += dp[j]
    return dp[t]


def print_allcomb(S, t, repeated=True):
    elm = [np.arange(0, t+1, s).reshape(-1, *[1]*(len(S)-1-i)) for i, s in enumerate(S)]
    idx = np.argwhere(np.sum(elm)==t)
    if not repeated:
        idx = idx[~(idx>1).any(1)]
        out = set()
    for subl in idx.tolist():
        temp = [lst[i] for i, n in enumerate(subl) for _ in range(n)]
        if repeated:
            print('+'.join(map(str, temp)))
        else:
            s = '+'.join(map(str, temp))
            if s not in out:
                print(s)
            out.add(s)


lst, t = [1, 3, 2, 4], 6
print_allcomb(lst, t)
print(count_dp(lst, t))
print('------')
print_allcomb(lst, t, False)

2+4
2+2+2
3+3
1+3+2
1+1+4
1+1+2+2
1+1+1+3
1+1+1+1+2
1+1+1+1+1+1
9
------
2+4
1+3+2

DFSで考えると，

def dfs(lst, t=6, res=(), s=None):
    if s is None: s = set()
    for x in lst:
        tpl = (*res, x)
        if x > t or x in s: continue
        elif x == t:
            yield tpl
            s.add(x)
        else: yield from dfs(lst[1:], t-x, tpl, s)


lst = [1, 3, 2, 4]
lst.sort()
list(dfs(lst))

[(1, 2, 3), (2, 4)]