How many ways can we make the change?

Software Development
#1

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 the total number of solutions, we can divide all set solutions into 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.

// Recursive C program for

// coin change problem.

#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;

}

Java

// Recursive java program for
// coin change problem.
import java.io.*;

class GFG {
    
    // Returns the count of ways we can 
    // sum S[0...m-1] coins to get sum n
    static 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
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 3};
        int m = arr.length;
        System.out.println( count(arr, m, 4));
        
        
    }

}

Output :

4