Coins and Denomination problem

Variation 1:

Given a infinite number of 25cents, 10 cents, 5 cents and 1 cent. WAP to calculate the number of ways of representing cents.

http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
http://algorithms.tutorialhorizon.com/dynamic-programming-coin-change-problem/

Variation 2:
Let us say we have an amount we have to pay someone: say $97. The given currency has notes worth $1, $5, $10 and $50. Now, what is the minimum number of currency notes with which the amount can be made? In this case, its eight: two $1 notes, a $5 note, four $10 notes and a $50 notes - eight in all.

http://www.geeksforgeeks.org/find-minimum-number-of-coins-that-make-a-change/
http://algorithms.tutorialhorizon.com/dynamic-programming-minimum-coin-change-problem/

Variation 3:
Write a function that takes an array of five integers, each of which is between 1 and 10, and returns the number of combinations of those integers that sum to 15. For example, calling the function with the array [1, 2, 3, 4, 5] should return 1, while calling it with [5, 5, 10, 2, 3] should return 4 (5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3). You may assume that the input has already been validated. 

Solution 1:

Idea is to use recursion. Let say for example we need to find number of ways in which we can represent 10 cents using the above given cents. Using recursion we would find out how many ways we could represent 10 cents using 1 cents which would be obviously be 1 and using this result we would try to build number of way to represent 10 using other cents. We would start with
MC(10, 25) -> MC(10, 10)  --------------> MC(10, 1)
                    ->MC(0, 5) -->MC(0, 1)     ->MC(5, 1)
                                                                ->MC(0, 1)

Method 1:Recursion

To count total number solutions, we can divide all set solutions in two sets.
1) Solutions that do not contain mth coin (or Sm).
2) Solutions that contain at least one Sm.
Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).




int count( int S[], int m, int n )

{

    // 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] );

}

Method 1:Dynamic Programming
We have taken one array and compute the number of ways a particular value can be arrived
With 2 taken 2,4,6,8,10 can be arrived in 1 ways
With 5 taken 5,10 can be arrived in 1 ways;but 10 can be arrived using 2 in 1 way.So total 2 ways now we can reach 10..Just like that we will continue from 5 to 10 and update array.
With 3 taken 3,6,9 can be arrived in 1 ways.Here when we come to 8 it can be arrived in using 2 -1 way,using 3-3+5[5 can be arrived in 1 ways]+3+3+2[2 can be arrived in 1 way]=So total 3 ways
Likewise we will continue...

The array table[sum+1] will have values as described below
Index      0  1  2  3  4  5  6  7  8  9  10
Values    1  0  0  0  0  0  0  0  0  0   0
j=2         1  0  1  0  1  0  1  0  1  0   1 table[j]=table[j]+ table[j-2]  j starts from index 2
j=5         1  0  1  0  1  1  1  1  1  1   2 table[j]=table[j]+ table[j-5]  j starts from index 5
j=3         1  0  1  1  1  2  2  2  3  3   3 table[j]=table[j]+ table[j-3]  j starts from index 3
j=6         1  0  1  1  1  2  3  2  4  4   5 table[j]=table[j]+ table[j-6]  j starts from index 6

So table[sum]=table[10]=5 is the answer

int count( int S[], int m, int sum )
{
      int table[sum+1];

    memset(table, 0, sizeof(table));

    table[0] = 1;

    for(int i=0; i<m; i++)
        for(int j=S[i]; j<=sum; j++)
            table[j] += table[j-S[i]];

    return table[sum];
}
Time Complexity: O(mn)

Solution 2:
http://www.seeingwithc.org/topic1html.html

Solution 3:[when coins are finite in variation 1]:
The solution to the problem can be understood as follows. Suppose I have a number x in the array and there I need to find the number of ways I can sum up to a value say 'S', then if there 'k' ways of getting a sum of 'S-x', the presence of the number 'x' gives us 'k' ways of getting a sum of 'S'.
This is because in the 'k' ways we can form a sum of S-x, we can also form a sum 'S' by adding 'x' to it. This way we have to find out all the possible ways. The base of the problem is that there is 1 way of forming a sum of 0.

int findSumComb(int a[], int sum,int length) // sum= the value whose sum is to be searched
                            //length= length of the array
{
    //initialize array with s[0] = 1 and rest 0s
        int s[sum+1]={1};

    for (int i = 0; i < length; ++i)
        for (int j = sum; j>=a[i]; --j )
            s[j] += s[j-a[i]];
    return s[sum];
}

s[sum 1] is an array that would contain the number of all possible sum combinations of a particular value, i.e. s[10] would contain no of all possible combinations of sum 10. We initiate the sum array with number of combinations for 0 as 1 i.e.sum[0]=1
Second loop is run for j>=a[i] because below that there will not be a valid index of the array sum.

Now if the number of ways of forming sum=x is let us say 4. We will have s[x] = 4. If there is a number a[i] in the given array such that j-a[i] = x then it means there are 4 ways of forming j i.e. by adding a[i] to the 4 ways of forming x and now s[j] =4.

The time complexity is O(n*sum) and space complexity id O(sum). Since it is a NP hard problem the solution is feasible only when the sum value is small.