Count all combinations of coins to make a given value sum using Recursion

Count all combinations of coins to make a given value sum Dynamic Programming (Memoization):

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.

Below is the Implementation of the above approach.

C++

// Recursive C++ program for
// coin change problem.
#include <bits/stdc++.h>
using namespace std;
 
// 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, sum - coins[n - 1])
           + count(coins, n - 1, sum);
}
 
// Driver code
int main()
{
    int i, j;
    int coins[] = { 1, 2, 3 };
    int n = sizeof(coins) / sizeof(coins[0]);
    int sum = 5;
 
    cout << " " << count(coins, n, sum);
 
    return 0;
}

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 function
int 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;
}

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

C#

// Recursive C# program for
// coin change problem.
using System;
 
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 program
    public static void Main()
    {
 
        int[] coins = { 1, 2, 3 };
        int n = coins.Length;
        Console.Write(count(coins, n, 5));
    }
}
// This code is contributed by Sam007

Javascript

<script>
// Recursive javascript program for
// coin change problem.
    
// Returns the count of ways we can 
// sum coins[0...n-1] coins to get sum "sum"
function 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
var coins = [1, 2, 3];
var n = coins.length;
document.write( count(coins, n, 5));
 
// This code is contributed by Amit Katiyar 
</script>

PHP

<?php
// Recursive PHP program for
// coin change problem.
 
// Returns the count of ways we can 
// sum coins[0...n-1] coins to get sum "sum"
function coun($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 coun($coins, $n - 1,$sum ) + 
           coun($coins, $n, $sum - $coins[$n - 1] );
}
 
    // Driver Code
    $coins = array(1, 2, 3);
    $n = count($coins);
    echo coun($coins, $n, 5); 
     
// This code is contributed by Sam007
?>

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

Output

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

Count all combinations of coins to make a given value sum (Coin Change II)

Given an integer array of coins[ ] of size N representing different types of denominations and an integer sum, the task is to count all combinations of coins to make a given value sum.

Note: Assume that you have an infinite supply of each type of coin.

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}.

Tags:

#Accolite #Microsoft #Morgan Stanley #Paytm #Samsung #Snapdeal #DSA #Dynamic Programming #Greedy #Mathematical #Accolite #Microsoft #Morgan Stanley #Paytm #Samsung #Snapdeal #Dynamic Programming #Greedy #Mathematical