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

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

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

The above recursive solution has Optimal Substructure and Overlapping Subproblems so Dynamic programming (Memoization) can be used to solve the problem. So 2D array can be used to store results of previously solved subproblems.

Follow the below steps to Implement the idea:

Create a 2D dp array to store the results of previously solved subproblems.
dp[i][j] will represent the number of distinct ways to make the sum j by using the first i coins.
During the recursion call, if the same state is called more than once, then we can directly return the answer stored for that state instead of calculating again.

Below is the implementation using the Memoization:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Recursive function to count the numeber of distinct ways
// to make the sum by using n coins
 
int count(vector<int>& coins, int n, int sum,
          vector<vector<int> >& dp)
{
    // Base Case
    if (sum == 0)
        return dp[n][sum] = 1;
 
    // If number of coins is 0 or sum is less than 0 then
    // there is no way to make the sum.
    if (n == 0 || sum < 0)
        return 0;
 
    // If the subproblem is previously calculated then
    // simply return the result
    if (dp[n][sum] != -1)
        return dp[n][sum];
 
    // Two options for the current coin
    return dp[n][sum]
           = count(coins, n, sum - coins[n - 1], dp)
             + count(coins, n - 1, sum, dp);
}
int32_t main()
{
    int tc = 1;
    // cin >> tc;
    while (tc--) {
        int n, sum;
        n = 3, sum = 5;
        vector<int> coins = { 1, 2, 3 };
        // 2d dp array to store previously calculated
        // results
        vector<vector<int> > dp(n + 1,
                                vector<int>(sum + 1, -1));
        int res = count(coins, n, sum, dp);
        cout << res << endl;
    }
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG {
    // Recursive function to count the numeber of distinct
    // ways to make the sum by using n coins
    static int count(int[] coins, int sum, int n,
                     int[][] dp)
    {
      // Base Case
        if (sum == 0)
            return dp[n][sum] = 1;
       
      // If number of coins is 0 or sum is less than 0 then
        // there is no way to make the sum.
        if (n == 0 || sum<0)
            return 0;
 
        // If the subproblem is previously calculated then
        // simply return the result
        if (dp[n][sum] != -1)
            return dp[n][sum];
 
       // Two options for the current coin
        return dp[n][sum]
            = count(coins, sum - coins[n - 1], n, dp)
              + count(coins, sum, n - 1, dp);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int tc = 1;
        while (tc != 0) {
            int n, sum;
            n = 3;
            sum = 5;
            int[] coins = { 1, 2, 3 };
            int[][] dp = new int[n + 1][sum + 1];
            for (int[] row : dp)
                Arrays.fill(row, -1);
            int res = count(coins, sum, n, dp);
            System.out.println(res);
            tc--;
        }
    }
}

C#

// C# program for the above approach
using System;
public class GFG {
    // Recursive function to count the numeber of distinct
    // ways to make the sum by using n coins
    static int count(int[] coins, int sum, int n,
                     int[, ] dp)
    { 
      // Base Case
        if (sum == 0)
            return dp[n, sum] = 1;
       
      // If number of coins is 0 or sum is less than 0 then
        // there is no way to make the sum.
        if (n == 0 || sum < 0)
            return 0;
       
      // If the subproblem is previously calculated then
        // simply return the result
        if (dp[n, sum] != -1)
            return dp[n, sum];
       
       // Two options for the current coin
        return dp[n, sum]
            = count(coins, sum - coins[n - 1], n, dp)
              + count(coins, sum, n - 1, dp);
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int tc = 1;
        while (tc != 0) {
            int n, sum;
            n = 3;
            sum = 5;
            int[] coins = { 1, 2, 3 };
            int[, ] dp = new int[n + 1, sum + 1];
            for (int j = 0; j < n + 1; j++) {
                for (int l = 0; l < sum + 1; l++)
                    dp[j, l] = -1;
            }
            int res = count(coins, sum, n, dp);
            Console.WriteLine(res);
            tc--;
        }
    }
}

Javascript

// javascript program for the above approach
 
    // Recursive function to count the numeber of distinct ways
    // to make the sum by using n coins
    function count(coins , sum , n,  dp) {
     
        // Base Case
        if (sum == 0)
            return dp[n][sum] = 1;
             
       // If number of coins is 0 or sum is less than 0 then
        // there is no way to make the sum.
        if (n == 0 || sum<0)
            return 0;
             
         // If the subproblem is previously calculated then
        // simply return the result
        if (dp[n][sum] != -1)
            return dp[n][sum];
             
          // Two options for the current coin 
          return dp[n][sum] = count(coins, sum - coins[n - 1], n, dp) + count(coins, sum, n - 1, dp);
         
    }
 
    // Driver code
     
        var tc = 1;
        while (tc != 0) {
            var n, sum;
            n = 3;
            sum = 5;
            var coins = [ 1, 2, 3 ];
            var dp = Array(n+1).fill().map(() => Array(sum+1).fill(-1));
             
            var res = count(coins, sum, n, dp);
            console.log(res);
            tc--;
        }

Python3

# Python program for the above approach
 
# Recursive function to count the numeber of distinct ways
# to make the sum by using n coins
 
 
def count(coins, sum, n, dp):
  # Base Case
    if (sum == 0):
        dp[n][sum] = 1
        return dp[n][sum]
 
     # If number of coins is 0 or sum is less than 0 then there is no way to make the sum.
    if (n == 0 or sum < 0):
        return 0
 
     # If the subproblem is previously calculated then simply return the result
    if (dp[n][sum] != -1):
        return dp[n][sum]
 
      # Two options for the current coin
 
    dp[n][sum] = count(coins, sum - coins[n - 1], n, dp) + \
        count(coins, sum, n - 1, dp)
 
    return dp[n][sum]
 
 
# Driver code
if __name__ == '__main__':
    tc = 1
    while (tc != 0):
        n = 3
        sum = 5
        coins = [1, 2, 3]
        dp = [[-1 for i in range(sum+1)] for j in range(n+1)]
        res = count(coins, sum, n, dp)
        print(res)
        tc -= 1

Output

Time Complexity: O(N*sum), where N is the number of coins and sum is the target sum.
Auxiliary Space: O(N*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