What is Java Program for Coin Change using Recursion?

In this article, we will learn Java Program for Coin Change using Recursion,This free Java tutorial for complete beginners will help you learn Java from scratch.

Java Program for Coin Change using Recursion

Java Program for Coin Change using Dynamic Programming (Memoization) :

Recurrence Relation:

count(coins,n,sum) = count(coins,n,sum-count[n-1]) + count(coins,n-1,sum)

For each coin, there are 2 options.

Include the current coin: Subtract the current coin’s denomination from the target sum and call the count function recursively with the updated sum and the same set of coins i.e., count(coins, n, sum – coins[n-1] )
Exclude the current coin: Call the count function recursively with the same sum and the remaining coins. i.e., count(coins, n-1,sum ).

The final result will be the sum of both cases.

Base case:

If the target sum (sum) is 0, there is only one way to make the sum, which is by not selecting any coin. So, count(0, coins, n) = 1.
If the target sum (sum) is negative or no coins are left to consider (n == 0), then there are no ways to make the sum, so count(sum, coins, 0) = 0.
Coin Change | DP-7

Below is the Implementation of the above approach:

Java

// Recursive JAVA program for
// coin change problem.
import java.util.*;
class GFG {
 
    // Returns the count of ways we can
    // sum coins[0...n-1] coins to get sum "sum"
    static int count(int coins[], int n, int sum)
    {
 
        // If sum is 0 then there is 1 solution
        // (do not include any coin)
        if (sum == 0)
            return 1;
 
        // If sum is less than 0 then no
        // solution exists
        if (sum < 0)
            return 0;
 
        // If there are no coins and sum
        // is greater than 0, then no
        // solution exist
        if (n <= 0)
            return 0;
 
        // count is sum of solutions (i)
        // including coins[n-1] (ii) excluding coins[n-1]
        return count(coins, n - 1, sum)
            + count(coins, n, sum - coins[n - 1]);
    }
 
    // Driver code
    public static void main(String args[])
    {
        int coins[] = { 1, 2, 3 };
        int n = coins.length;
 
        System.out.println(count(coins, n, 5));
    }
}
 
// This code is contributed by jyoti369

Output

Time Complexity: O(2^sum)
Auxiliary Space: O(sum)

Java Program for Coin Change | DP-7

Write a Java program for a given integer array of coins[ ] of size N representing different types of denominations and an integer sum, the task is to find the number of ways to make a sum by using different denominations.

Examples:

Input: sum = 4, coins[] = {1,2,3},
Output: 4
Explanation: there are four solutions: {1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}.

Input: sum = 10, coins[] = {2, 5, 3, 6}
Output: 5
Explanation: There are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}.