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