Overlapping Subproblems

Software Development
#1

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