Coin Change

Source

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

1) Optimal Substructure
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).

Therefore, the problem has optimal substructure property as the problem can be solved using solutions to subproblems.

2) Overlapping Subproblems
Following is a simple recursive implementation of the Coin Change problem. The implementation simply follows the recursive structure mentioned above.

#include<stdio.h>   // Returns the count of ways we can sum  S[0...m-1] coins to get sum n 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] ); }   // Driver program to test above function int main() {     int i, j;     int arr[] = {1, 2, 3};     int m = sizeof(arr)/sizeof(arr[0]);     printf("%d ", count(arr, m, 4));     getchar();     return 0; }

It should be noted that the above function computes the same subproblems again and again. See the following recursion tree for S = {1, 2, 3} and n = 5.
The function C({1,3}, 1) is called two times. If we draw the complete tree, then we can see that there are many subproblems being called more than once.

C() --> count()
                              C({1,2,3}, 5)
                           /                \
                         /                   \
             C({1,2,3}, 2)                 C({1,2}, 5)
            /     \                        /         \
           /        \                     /           \
C({1,2,3}, -1)  C({1,2}, 2)        C({1,2}, 3)    C({1}, 5)
               /     \            /    \            /     \
             /        \          /      \          /       \
    C({1,2},0)  C({1},2)   C({1,2},1) C({1},3)    C({1}, 4)  C({}, 5)
                   / \      / \       / \        /     \
                  /   \    /   \     /   \      /       \
                .      .  .     .   .     .   C({1}, 3) C({}, 4)
                                               /  \
                                              /    \
                                             .      .

Since same suproblems are called again, this problem has Overlapping Subprolems property. So the Coin Change problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array table[][] in bottom up manner.

Dynamic Programming Solution

#include<stdio.h>   int count( int S[], int m, int n ) {     int i, j, x, y;       // We need n+1 rows as the table is consturcted in bottom up manner using     // the base case 0 value case (n = 0)     int table[n+1][m];       // Fill the enteries for 0 value case (n = 0)     for (i=0; i<m; i++)         table[0][i] = 1;       // Fill rest of the table enteries in bottom up manner     for (i = 1; i < n+1; i++)     {         for (j = 0; j < m; j++)         {             // Count of solutions including S[j]             x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;               // Count of solutions excluding S[j]             y = (j >= 1)? table[i][j-1]: 0;               // total count             table[i][j] = x + y;         }     }     return table[n][m-1]; }   // Driver program to test above function int main() {     int arr[] = {1, 2, 3};     int m = sizeof(arr)/sizeof(arr[0]);     int n = 4;     printf(" %d ", count(arr, m, n));     return 0; }

Time Complexity: O(mn)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


typedef unsigned uint32_t;


void
displayChange(uint32_t  s[],
              uint32_t  n,
              uint32_t* counter)
{
    assert(counter != NULL);
    printf("{");
    for (uint32_t ii = 0; ii < n; ii++) {
        for (uint32_t jj = 0; jj < counter[ii]; jj++) {
            printf("%u ", s[ii]);
        }
    }
    printf("}\n");
}              
              
void
getChange(uint32_t  s[],
          uint32_t  sizeS,
          uint32_t  N,
          uint32_t  currentN,
          uint32_t  index,
          uint32_t* counter)
{
    assert(counter != NULL);
    
    if (index >= sizeS) {
        return;
    }
    
    if (currentN > N) {
        return;
    }
    
    if (currentN == N) {
        displayChange(s, sizeS, counter);
return;
    }
    
    // include me
    counter[index] += 1;
    getChange(s,
              sizeS,
              N,
              currentN + s[index],
              index, // dont incement so that current can be repeated
              counter);
    counter[index] -= 1;
    
    getChange(s,
              sizeS,
              N,
              currentN,
              index + 1,
              counter);
}


void getChangeCombinations(uint32_t s[],
                           uint32_t sizeS,
                           uint32_t N)
{
    uint32_t* pCounter = (uint32_t* )calloc(sizeof(uint32_t), N);
    if (pCounter == NULL) {
        return;
    }
    
    getChange(s,
              sizeS,
              N,
              0,
              0,
              pCounter);
          
    free(pCounter);
    pCounter = NULL;
}
                          
int
main()
{ uint32_t s[] = {1, 3, 2};
int N = 4;
getChangeCombinations(s, sizeof(s)/ sizeof(uint32_t), N);
return 0;
}