# 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