Java Program for Coin Change using Recursion
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 |
5
Time Complexity: O(2sum)
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}.