3

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?

irrelephant
  • 4,081
  • 2
  • 23
  • 41
abhi
  • 327
  • 1
  • 7
  • 12
  • You already figured it is related to [subset sum problem](http://en.wikipedia.org/wiki/Subset_sum_problem). It is even harder (reduceable) then subset-sum problem with the reduction: if there are x>0 solutions, accept - otherwise, reject. So this problem is [NP-Hard](http://en.wikipedia.org/wiki/NP-hard) as well, there is no known *efficient* solution, in the standard definition of efficient (polynomial). Do you have other definition for efficient for your case? If so - specify it please. – amit Aug 13 '12 at 07:42
  • @amit Why wouldn't dynamic programming work here? – irrelephant Aug 13 '12 at 07:43
  • @amit i just want to know is there any polynomial time solution. – abhi Aug 13 '12 at 07:48
  • 3
    This is a solution to an identical problem: http://www.algorithmist.com/index.php/Coin_Change – irrelephant Aug 13 '12 at 07:52
  • 2
    @irrelephant: The problem is NP-Hard, the DP algorithm will most likely yield **pseudo polynomial** solution, which is not polynomial, and is not considered *efficient* in its standard definition. If one can find polynomial solution to an NP-Hard Problem, it will prove `P=NP` (which is probably not the case). – amit Aug 13 '12 at 07:54

1 Answers1

3

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]
devnum
  • 198
  • 8