予有含自然数和目标吨其是数字的组S.我想知道我们怎样才能找到的这些号码这总计为靶T的可能的组合的数量。若干可采取任何数量的时间和任何数目的数字可以采取用于获取在总和等于目标万吨。

I have a set S containing natural numbers and a target t which is an number. I want to know how can we find the number of possible combinations of these numbers which sums up to target t. A number can be taken any number of times and any number of numbers can be taken for getting the sum equal to the target 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

什么是有效的算法呢？

What can be the efficient algorithm for this?

推荐答案

如果目标是相当小的，可以用动态规划得到O（| S | * t）的解决方案。下面是一个示例code在Python：

If the target is reasonably small, you can use dynamic programming to obtain an O(|S| * t) solution. Here is a sample code in 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]