Maximum no of ways to make change for an amount

Max possible ways for Coin Change Problem:

Given set of n coins what is the maximum no of ways to make an amount P.

This problem can be solved using Dynamic programming, we need to find out the maximum no of ways for the amount less than P and add all of them.

Coins = {1,2,5}
Amount =4

C(i) = Sum(C(j)) 1<j<Sum


The idea is to add all possible ways using each denomination.
For Ex:

{1,2,5} are the denomination, then to make change of 4, we do the following

First to make a change of 1 using S[0], which 1.
To make change of 2 using 1 is 1
To make change of 3 using 1 is 1
To make change of 4 using 1 is 1
Now to make change of 1 using 2 is not possible
To make change of 2 using 2 is 1 and we add this to previous count using 1, so total solution to make amount of 2 is 2.
To make change of 2 using 2 is is 1, and this will add up to making amount of 2 using 2. So total ways is 2
To make change of 3 using 2 is 0, we can't get 3 using only 2, we need to use 1, {1,2} or {2,1}.
  So to make amount of 3 is only 1 way.
To make change of 4 using 2 is 1, total ways to make amount of 4 is 2.
int count( int S[], int m, int Sum ) {
    // table[i] will be storing the number of solutions for
    // value i. We need n+1 rows as the table is consturcted
    // in bottom up manner using the base case (n = 0)   
    int table[16];   
    // Initialize all table values as 0  
    memset(table, 0, sizeof(table));   
    // Base case (If given value is 0)   
    table[0] = 1;    
    // Pick all coins one by one and update the table[] values
    // after the index greater than or equal to the value of the 
    // picked coin  
    for(int i=0; i<m; i++) 
    {
    for(int j=S[i]; j<=Sum; j++)
    {
        table[j] += table[j-S[i]];
    }
    }
    return table[Sum];
}