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

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 Dynamic Programming (Space Optimized):

We can use the following steps to implement the dynamic programming(tabulation) approach for Coin Change.

Create a 2D dp array with rows and columns equal to the number of coin denominations and target sum.
dp[0][0] will be set to 1 which represents the base case where the target sum is 0, and there is only one way to make the change by not selecting any coin.
Iterate through the rows of the dp array (i from 1 to n), representing the current coin being considered.
- The inner loop iterates over the target sums (j from 0 to sum).
  - Add the number of ways to make change without using the current coin, i.e., dp[i][j] += dp[i-1][j].
  - Add the number of ways to make change using the current coin, i.e., dp[i][j] += dp[i][j-coins[i-1]].
dp[n][sum] will contain the total number of ways to make change for the given target sum using the available coin denominations.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
 
using namespace std;
 
// Returns total distinct ways to make sum using n coins of
// different denominations
int count(vector<int>& coins, int n, int sum)
{
    // 2d dp array where n is the number of coin
    // denominations and sum is the target sum
    vector<vector<int> > dp(n + 1, vector<int>(sum + 1, 0));
 
    // Represents the base case where the target sum is 0,
    // and there is only one way to make change: by not
    // selecting any coin
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= sum; j++) {
 
            // Add the number of ways to make change without
            // using the current coin,
            dp[i][j] += dp[i - 1][j];
 
            if ((j - coins[i - 1]) >= 0) {
 
                // Add the number of ways to make change
                // using the current coin
                dp[i][j] += dp[i][j - coins[i - 1]];
            }
        }
    }
    return dp[n][sum];
}
 
// Driver Code
int main()
{
    vector<int> coins{ 1, 2, 3 };
    int n = 3;
    int sum = 5;
    cout << count(coins, n, sum);
    return 0;
}

Java

import java.util.*;
 
public class CoinChangeWays {
    // Returns total distinct ways to make sum using n coins of
    // different denominations
    static int count(List<Integer> coins, int n, int sum) {
        // 2D dp array where n is the number of coin
        // denominations and sum is the target sum
        int[][] dp = new int[n + 1][sum + 1];
 
        // Represents the base case where the target sum is 0,
        // and there is only one way to make change: by not
        // selecting any coin
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= sum; j++) {
                // Add the number of ways to make change without
                // using the current coin
                dp[i][j] += dp[i - 1][j];
 
                if ((j - coins.get(i - 1)) >= 0) {
                    // Add the number of ways to make change
                    // using the current coin
                    dp[i][j] += dp[i][j - coins.get(i - 1)];
                }
            }
        }
        return dp[n][sum];
    }
 
    // Driver Code
    public static void main(String[] args) {
        List<Integer> coins = Arrays.asList(1, 2, 3);
        int n = 3;
        int sum = 5;
        System.out.println(count(coins, n, sum));
    }
}
// This code is contributed by Veerendra_Singh_Rajpoot

C#

using System;
using System.Collections.Generic;
 
class Program {
    // Returns total distinct ways to make sum using n coins
    // of different denominations
    static int Count(List<int> coins, int n, int sum)
    {
        // 2d dp array where n is the number of coin
        // denominations and sum is the target sum
        int[, ] dp = new int[n + 1, sum + 1];
 
        // Represents the base case where the target sum is
        // 0, and there is only one way to make change: by
        // not selecting any coin
        dp[0, 0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= sum; j++) {
                // Add the number of ways to make change
                // without using the current coin
                dp[i, j] += dp[i - 1, j];
 
                if ((j - coins[i - 1]) >= 0) {
                    // Add the number of ways to make change
                    // using the current coin
                    dp[i, j] += dp[i, j - coins[i - 1]];
                }
            }
        }
        return dp[n, sum];
    }
 
    // Driver Code
    static void Main(string[] args)
    {
        List<int> coins = new List<int>{ 1, 2, 3 };
        int n = 3;
        int sum = 5;
        Console.WriteLine(Count(coins, n, sum));
    }
}

Javascript

function count(coins, n, sum) {
    // Create a 2D array dp where n is the number of coin denominations
    // and sum is the target sum
    let dp = new Array(n + 1).fill(0).map(() => new Array(sum + 1).fill(0));
 
    // Set the base case where the target sum is 0, and there is only one way to make change
    // by not selecting any coin
    dp[0][0] = 1;
 
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j <= sum; j++) {
            // Add the number of ways to make change without using the current coin
            dp[i][j] += dp[i - 1][j];
 
            if (j - coins[i - 1] >= 0) {
                // Add the number of ways to make change using the current coin
                dp[i][j] += dp[i][j - coins[i - 1]];
            }
        }
    }
 
    return dp[n][sum];
}
 
// Driver Code
let coins = [1, 2, 3];
let n = 3;
let sum = 5;
console.log(count(coins, n, sum));

Python3

# Function to calculate the total distinct ways to make a sum using n coins of different denominations
def count(coins, n, target_sum):
    # 2D dp array where n is the number of coin denominations and target_sum is the target sum
    dp = [[0 for j in range(target_sum + 1)] for i in range(n + 1)]
 
    # Represents the base case where the target sum is 0, and there is only one way to make change: by not selecting any coin
    dp[0][0] = 1
    for i in range(1, n + 1):
        for j in range(target_sum + 1):
            # Add the number of ways to make change without using the current coin
            dp[i][j] += dp[i - 1][j]
 
            if j - coins[i - 1] >= 0:
                # Add the number of ways to make change using the current coin
                dp[i][j] += dp[i][j - coins[i - 1]]
 
    return dp[n][target_sum]
 
# Driver Code
if __name__ == "__main__":
    coins = [1, 2, 3]
    n = 3
    target_sum = 5
    print(count(coins, n, target_sum))

Output

Time complexity : O(N*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