algorithm - 集合中数字重复的子集求和算法

Question

我有一个包含自然数的集合 S 和一个目标 t，它是一个数字。我想知道
我们如何才能找到这些数字的可能组合数量，这些数字总和为目标 t。
一个数字可以取任意次数，并且可以取任意数量的数字来获得
等于目标 t 的总和。

Example
target  6
Set s  {3,8,1,2}
Solution   3+3, 3+2+1, 1+1+1+3, 2+2+2, 2+1+1+2, 2+1+1+1+1, 1+1+1+1+1+1
Total No of solutions possible  7

什么是有效的算法？

Answer 1

如果目标相当小，您可以使用动态规划来获得 O(|S| * t) 解。这是 Python 中的示例代码：

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