C 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:
C
// Recursive C program for// coin change problem.#include <stdio.h>// Returns the count of ways we can// sum coins[0...n-1] coins to get sum "sum"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 program to test above functionint main(){ int i, j; int coins[] = { 1, 2, 3 }; int n = sizeof(coins) / sizeof(coins[0]); printf("%d ", count(coins, n, 5)); getchar(); return 0;} |
5
Time Complexity: O(2sum)
Auxiliary Space: O(sum)
C Program for Coin Change | DP-7
Write a C 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