Python 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:
Python3
# Recursive Python3 program for # coin change problem. # Returns the count of ways we can sum # coins[0...n-1] coins to get sum "sum" def count(coins, n, 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 program to test above function coins = [ 1 , 2 , 3 ] n = len (coins) print (count(coins, n, 5 )) # This code is contributed by Smitha Dinesh Semwal |
5
Time Complexity: O(2sum)
Auxiliary Space: O(sum)
Python Program for Coin Change | DP-7
Write a Python 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}.
Contact Us