Finding a all the combination of a number for a specific sum

Question

Array
A ={1,2,3}

For Sum value = 5
Possible Combination

{3,2} , {1,1,1,1,1} , {2,2,1} and all possiable one

here is my approach:

int count( int S[], int m, int n )
{
    // m is the size of the array and n is required sum
    // If n is 0 then there is 1 solution (do not include any coin)
    if (n == 0)
        return 1;

    // If n is less than 0 then no solution exists
    if (n < 0)
        return 0;

    // If there are no coins and n is greater than 0, then no solution exist
    if (m <=0 && n >= 1)
        return 0;

    // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}

My approach Disadvantage: : It have to recalculate the many combination again and again. So it the value of sum is very high so it is very slow.
I want to implement this using dynamic programming please provide me an explaination how can i store the calculated value so i can reuse it and reduce time of my program

Answer 1

I would do it differently:

1. generate coin array to match sum

   1. genere one coin type
      • start with the biggest one
      • add them as much as you can
      • but the sum must be <= then the target sum
      • if target sum is achieved store result
   2. recursively call step 1 for next lower coin
      • but remember last coin array state
      • if there is no coin=1 then sometimes the result will be invalid
   3. move to next combination
      • restore last coin array state
      • remove last coin from it
      • if there is none to remove then stop
      • else repeat step 2

2. count permutations/combinantions if also the order matters

   • so take valid result and permute it by rules of your problem
   • to get more solutions from it
   • it is faster then try every possibility in 1.

example (for 1.):

coins = { 5,2,1 }
sum=7

5 | 2 
5 | -     | 1 1
- | 2 2 2 | 1
- | 2 2   | 1 1 1
- | 2     | 1 1 1 1 1

• | separates recursion layer
• there is one recursion level per each coin type
• so you need memory for 3 array states in this case (the lengths depends on target sum)
• this is acceptable (I saw solutions with much worse space complexity for this problem)
• for very big Sums I would use RLE for memory conservations and speedup the process

[edit1] C++ source code

//---------------------------------------------------------------------------
void prn_coins(int *count,int *value,int coins) // just to output solution somewhere
    {
    int i;
    AnsiString s="";
    for (i=0;i<coins;i++)
     s+=AnsiString().sprintf("%ix%i ",count[i],value[i]);
    Form1->mm_log->Lines->Add(s);
    }
//---------------------------------------------------------------------------
void get_coins(int *count,int *value,int coins,int sum,int ix=0,int si=0)
    {
    if (ix>=coins) return; // exit
    if (ix==0)  // init:
        {
        ix=0; // first layer
        si=0; // no sum in solution for now
        for (int i=0;i<coins;i++) count[i]=0; // no coins in solution for now
        }
    //1. genere actal coint type value[]
    count[ix]=(sum-si)/value[ix];   // as close to sum as can
    si+=value[ix]*count[ix];        // update actual sum
    for(;;)
        {
        //2. recursion call
        if (si==sum) prn_coins(count,value,coins);
        else get_coins(count,value,coins,sum,ix+1,si);
        //3. next combination
        if (count[ix]) { count[ix]--; si-=value[ix]; }
        else break;
        }
    }
//---------------------------------------------------------------------------
void main()
    {
    const int _coins=3;             // coin types
    int value[_coins]={5,2,1};      // coin values (must be in descending order !!!)
    int count[_coins]={0,0,0};      // coin count in actual solution (RLE)
    get_coins(count,value,_coins,7);
    }
//-------------------------------------------------------------------------

• this code took ~3ms on mine HW setup
• just change the prn_coins function to your form of print (I used VCL memo and AnsiSring)
• in this code the solution state is automaticly rewriten back to previous state
• so no need to further memoize (else it would be necessary to copy the count array before and after recursion)
• Now the permutation step would be necessary if:
• each coin is unique? (1 1 2 5) != (1 1 2 5)
• or just coin type? (1 1 2 5) != (1 2 1 5)
• in that case just add the permutation code to prn_coins function ...
• but that is different question ...

Answer 2

A very simple change to your solution would be to just add "memoization".

Considering the array S fixed the result of your function just depends on m and n. Therefore you can do the following small change:

int count( int S[], int m, int n ) {
    ...
    if (cache[m][n] == -1) {
        cache[m][n] = count( S, m - 1, n ) + count( S, m, n-S[m-1] );
    }
    return cache[m][n];
}

This way you're only compute the result once for each distinct pair of values m and n.

The idea is to keep a 2d array indexed by (m,n) all initialized to -1 (meaning "not yet computed"). When you're about to compute a value in count you first check if the value has not been computed yet and if this is the case you also store the result in the 2d matrix so you will not recompute the same number again in the future.

Answer 3

For dynamic programming you need to generalise your problem. Let S(a, x) be all possible sums of value x, only using values from A starting at index a. Your original problem is S(0, X).

Since you have a discrete function with two parameters you can store its outcomes in a 2d array.

There are some simple cases: there is no solution for a = A.length and X > 0.

There is the set only containing an empty sum for X = 0.

Now, you should find a recursive formula for the other cases and fill the table in such a way that the indices you depend on have already been calculated (hint: consider looping backwards).