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]