Coin Change - Minimum Coins to Make Sum

Last Updated : 14 Mar, 2025

Try it on GfG Practice

Given an array of coins[] of size n and a target value sum, where coins[i] represent the coins of different denominations. You have an infinite supply of each of the coins. The task is to find the minimum number of coins required to make the given value sum. If it is not possible to form the sum using the given coins, return -1.

Examples:

Input: coins[] = [25, 10, 5], sum = 30
Output: 2
Explanation : Minimum 2 coins needed, 25 and 5
Input: coins[] = [9, 6, 5, 1], sum = 19
Output: 3
Explanation: 19 = 9 + 9 + 1
Input: coins[] = [5, 1], sum = 0
Output: 0
Explanation: For 0 sum, we do not need a coin
Input: coins[] = [4, 6, 2], sum = 5
Output: -1
Explanation: Not possible to make the given sum.

Table of Content

[Naive Approach ] Using Recursion – O(n^sum) Time and O(sum) Space
[Better Approach 1] Using Top-Down DP (Memoization) - O(n*sum) Time and O(n*sum) Space
[Better Approach 2] Using Bottom-Up DP (Tabulation) - O(n*sum) Time and O(n*sum) Space
[Expected Approach] Using Space Optimized DP – O(n*sum) Time and O(sum) Space

[Naive Approach ] Using Recursion – O(n^sum) Time and O(sum) Space

This problem is a variation of the problem Coin Change Problem. Here instead of finding the total number of possible solutions, we need to find the solution with the minimum number of coins.
The idea is to find the minimum number of coins required to reach the target sum by trying each coin denomination in the coins[] array. Starting from the target sum, for each coin coins[i], we can either include it or exclude it. If we include it, we subtract its value from sum and recursively try to make the remaining amount with the same coin denominations. If we exclude it, we move to the next coin in the list.

Mathematically the recurrence relation will look like the following:

minCoins(i, sum, coins) = min(1 + minCoins(i, sum-coins[i], coins), minCoins(i+1, sum, coins))
Base cases:
minCoins(i, sum, coins) = 0, if sum = 0.
minCoins(i, sum, coins) = INTEGER MAX, if sum < 0 or i == size of coins.

C++

// C++ program to find minimum of coins
// to make a given change sum
#include<bits/stdc++.h>
using namespace std;

int minCoinsRecur(int i, int sum, vector<int> &coins) {
    
    // base case
    if (sum == 0) return 0;
    if (sum <0 || i == coins.size()) return INT_MAX;
    
    int take = INT_MAX;
    
    // take a coin only if its value
    // is greater than 0.
    if (coins[i]>0) {
        take = minCoinsRecur(i, sum-coins[i], coins);
        if (take != INT_MAX) take++;
    }
    
    // not take the coin
    int noTake = minCoinsRecur(i+1, sum, coins);
    
    return min(take, noTake);
}

int minCoins(vector<int> &coins, int sum) {

   int res = minCoinsRecur(0, sum, coins);
   return res!=INT_MAX?res:-1;
}

int main() {
    vector<int> coins =  {9, 6, 5, 1};
    int sum = 19;
    cout << minCoins(coins, sum);
    return 0;
}

Java

// Java program to find minimum of coins
// to make a given change sum

import java.util.Arrays;

class GfG {

    static int minCoinsRecur(int i, int sum, int[] coins) {
        
        // base case
        if (sum == 0) return 0;
        if (sum < 0 || i == coins.length) return Integer.MAX_VALUE;
        
        int take = Integer.MAX_VALUE;
        
        // take a coin only if its value
        // is greater than 0.
        if (coins[i] > 0) {
            take = minCoinsRecur(i, sum - coins[i], coins);
            if (take != Integer.MAX_VALUE) take++;
        }
        // not taking the coins
        int noTake = minCoinsRecur(i + 1, sum, coins);
        
        return Math.min(take, noTake);
    }

    static int minCoins(int[] coins, int sum) {
        int ans = minCoinsRecur(0, sum, coins);
        return ans != Integer.MAX_VALUE ? ans : -1;
    }

    public static void main(String[] args) {
        int[] coins = {9, 6, 5, 1};
        int sum = 19;
        System.out.println(minCoins(coins, sum));
    }
}

Python

# Python program to find minimum of coins
# to make a given change sum

def minCoinsRecur(i, sum, coins):
    
    # base case
    if sum == 0:
        return 0
    if sum < 0 or i == len(coins):
        return float('inf')
    
    take = float('inf')
    
    # take a coin only if its value
    # is greater than 0.
    if coins[i] > 0:
        take = minCoinsRecur(i, sum - coins[i], coins)
        if take != float('inf'):
            take += 1
    #not taking the coin
    noTake = minCoinsRecur(i + 1, sum, coins)
    
    return min(take, noTake)

def minCoins(coins, sum):
    ans = minCoinsRecur(0, sum, coins)
    return ans if ans != float('inf') else -1

if __name__ == "__main__":
    coins = [9, 6, 5, 1]
    sum = 19
    print(minCoins(coins, sum))

C#

// C# program to find minimum of coins
// to make a given change sum

using System;

class GfG {

    static int minCoinsRecur(int i, int sum, int[] coins) {
        
        // base case
        if (sum == 0) return 0;
        if (sum < 0 || i == coins.Length) return int.MaxValue;
        
        int take = int.MaxValue;
        
        // take a coin only if its value
        // is greater than 0.
        if (coins[i] > 0) {
            take = minCoinsRecur(i, sum - coins[i], coins);
            if (take != int.MaxValue) take++;
        }
        // not taking the coin
        int noTake = minCoinsRecur(i + 1, sum, coins);
        
        return Math.Min(take, noTake);
    }

    static int minCoins(int[] coins, int sum) {
        int ans = minCoinsRecur(0, sum, coins);
        return ans != int.MaxValue ? ans : -1;
    }

    static void Main(string[] args) {
        int[] coins = { 9, 6, 5, 1 };
        int sum = 19;
        Console.WriteLine(minCoins(coins, sum));
    }
}

JavaScript

// JavaScript program to find minimum of coins
// to make a given change sum

function minCoinsRecur(i, sum, coins) {
    
    // base case
    if (sum === 0) return 0;
    if (sum < 0 || i === coins.length) return Number.MAX_VALUE;
    
    let take = Number.MAX_VALUE;
    
    // take a coin only if its value
    // is greater than 0.
    if (coins[i] > 0) {
        take = minCoinsRecur(i, sum - coins[i], coins);
        if (take !== Number.MAX_VALUE) take++;
    }
    // not taking the coin 
    let noTake = minCoinsRecur(i + 1, sum, coins);
    
    return Math.min(take, noTake);
}

function minCoins(coins, sum) {
    let ans = minCoinsRecur(0, sum, coins);
    return ans !== Number.MAX_VALUE ? ans : -1;
}

// Driver code 
const coins = [9, 6, 5, 1];
const sum = 19;
console.log(minCoins(coins, sum));

Output

[Better Approach 1] Using Top-Down DP (Memoization) - O(nsum) Time and O(nsum) Space

If we notice carefully, we can observe that the above recursive solution holds the following two properties of Dynamic Programming:

1. Optimal Substructure:
Minimum number of ways to make sum at index i, i.e., minCoins(i, sum, coins), depends on the optimal solutions of the subproblems minCoins(i, sum-coins[i], coins) , and minCoins(i+1, sum, coins). By comparing these optimal substructures, we can efficiently calculate the minimum number of coins to make target sum at index i.
2. Overlapping Subproblems:
While applying a recursive approach in this problem, we notice that certain subproblems are computed multiple times.

There are only are two parameters: i and sum that changes in the recursive solution. So we create a 2D matrix of size n*(sum+1) for memoization.
We initialize this matrix as -1 to indicate nothing is computed initially.
Now we modify our recursive solution to first check if the value is -1, then only make recursive calls. This way, we avoid re-computations of the same subproblems.

C++

// C++ program to find minimum of coins
// to make a given change sum
#include<bits/stdc++.h>
using namespace std;

int minCoinsRecur(int i, int sum, vector<int> &coins, vector<vector<int>> &memo) {

    // base case
    if (sum == 0) return 0;
    if (sum <0 || i == coins.size()) return INT_MAX;
    
    if (memo[i][sum]!=-1) return memo[i][sum];
    
    int take = INT_MAX;
    
    // take a coin only if its value
    // is greater than 0.
    if (coins[i]>0) {
        take = minCoinsRecur(i, sum-coins[i], coins, memo);
        if (take != INT_MAX) take++;
    }
    // not take the coins
    int noTake = minCoinsRecur(i+1, sum, coins, memo);
    
    return memo[i][sum] = min(take, noTake);
}

int minCoins(vector<int> &coins, int sum) {
    vector<vector<int>> memo(coins.size(), vector<int>(sum+1, -1));
    int res = minCoinsRecur(0, sum, coins, memo);
    return res!=INT_MAX?res:-1;
}

int main() {
    vector<int> coins =  {9, 6, 5, 1};
    int sum = 19;
    cout << minCoins(coins, sum);
    return 0;
}

Java

// Java program to find minimum of coins
// to make a given change sum

import java.util.Arrays;

class GfG {

    static int minCoinsRecur(int i, int sum, int[] coins, int[][] memo) {

        // base case
        if (sum == 0) return 0;
        if (sum < 0 || i == coins.length) return Integer.MAX_VALUE;
        
        if (memo[i][sum] != -1) return memo[i][sum];
        
        int take = Integer.MAX_VALUE;
        
        // take a coin only if its value
        // is greater than 0.
        if (coins[i] > 0) {
            take = minCoinsRecur(i, sum - coins[i], coins, memo);
            if (take != Integer.MAX_VALUE) take++;
        }
        // not take the coin 
        int noTake = minCoinsRecur(i + 1, sum, coins, memo);
        
        return memo[i][sum] = Math.min(take, noTake);
    }

    static int minCoins(int[] coins, int sum) {
        int[][] memo = new int[coins.length][sum + 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        int ans = minCoinsRecur(0, sum, coins, memo);
        return ans != Integer.MAX_VALUE ? ans : -1;
    }

    public static void main(String[] args) {
        int[] coins = {9, 6, 5, 1};
        int sum = 19;
        System.out.println(minCoins(coins, sum));
    }
}

Python

# Python program to find minimum of coins
# to make a given change sum

def minCoinsRecur(i, sum, coins, memo):
    
    # base case
    if sum == 0:
        return 0
    if sum < 0 or i == len(coins):
        return float('inf')
    
    if memo[i][sum] != -1:
        return memo[i][sum]
    
    take = float('inf')
    
    # take a coin only if its value
    # is greater than 0.
    if coins[i] > 0:
        take = minCoinsRecur(i, sum - coins[i], coins, memo)
        if take != float('inf'):
            take += 1
    #not take the coins 
    noTake = minCoinsRecur(i + 1, sum, coins, memo)
    
    memo[i][sum] = min(take, noTake)
    return memo[i][sum]

def minCoins(coins, sum):
    memo = [[-1] * (sum + 1) for _ in range(len(coins))]
    ans = minCoinsRecur(0, sum, coins, memo)
    return ans if ans != float('inf') else -1

if __name__ == "__main__":
    coins = [9, 6, 5, 1]
    sum = 19
    print(minCoins(coins, sum))

C#

// C# program to find minimum of coins
// to make a given change sum

using System;

class GfG {

    static int minCoinsRecur(int i, int sum, int[] coins, int[,] memo) {

        // base case
        if (sum == 0) return 0;
        if (sum < 0 || i == coins.Length) return int.MaxValue;
        
        if (memo[i, sum] != -1) return memo[i, sum];
        
        int take = int.MaxValue;
        
        // take a coin only if its value
        // is greater than 0.
        if (coins[i] > 0) {
            take = minCoinsRecur(i, sum - coins[i], coins, memo);
            if (take != int.MaxValue) take++;
        }
        // not take the coins 
        int noTake = minCoinsRecur(i + 1, sum, coins, memo);
        
        memo[i, sum] = Math.Min(take, noTake);
        return memo[i, sum];
    }

    static int minCoins(int[] coins, int sum) {
        int[,] memo = new int[coins.Length, sum + 1];
        for (int i = 0; i < coins.Length; i++)
            for (int j = 0; j <= sum; j++)
                memo[i, j] = -1;
        int ans = minCoinsRecur(0, sum, coins, memo);
        return ans != int.MaxValue ? ans : -1;
    }

    static void Main(string[] args) {
        int[] coins = { 9, 6, 5, 1 };
        int sum = 19;
        Console.WriteLine(minCoins(coins, sum));
    }
}

JavaScript

// JavaScript program to find minimum of coins
// to make a given change sum

function minCoinsRecur(i, sum, coins, memo) {

    // base case
    if (sum === 0) return 0;
    if (sum < 0 || i === coins.length) 
    return Number.MAX_VALUE;
    
    if (memo[i][sum] !== -1) return memo[i][sum];
    
    let take = Number.MAX_VALUE;
    
    // take a coin only if its value
    // is greater than 0.
    if (coins[i] > 0) {
        take = minCoinsRecur(i, sum - coins[i], coins, memo);
        if (take !== Number.MAX_VALUE) take++;
    }
    // not take the coin 
    let noTake = minCoinsRecur(i + 1, sum, coins, memo);
    
    memo[i][sum] = Math.min(take, noTake);
    return memo[i][sum];
}

function minCoins(coins, sum) {
    const memo = Array.from({ length: coins.length }
    , () => Array(sum + 1).fill(-1));
    const ans = minCoinsRecur(0, sum, coins, memo);
    return ans !== Number.MAX_VALUE ? ans : -1;
}

// Driver code 
const coins = [9, 6, 5, 1];
const sum = 19;
console.log(minCoins(coins, sum));

Output

[Better Approach 2] Using Bottom-Up DP (Tabulation) - O(nsum) Time and O(nsum) Space

The idea is to fill the DP table based on previous values. For each coin, we either include it or exclude it to compute the minimum number of coins needed for each sum. The table is filled in an iterative manner from i = n-1 to i = 0 and for each sum from 1 to sum.
The dynamic programming relation is as follows:
if (sum-coins[i]) is greater than 0, then dp[i][sum] = min(1+dp[i][sum-coins[i]], dp[i+1][sum])
else dp[i][sum] = dp[i+1][sum].

C++

// C++ program to find minimum of coins
// to make a given change sum
#include<bits/stdc++.h>
using namespace std;

int minCoins(vector<int> &coins, int sum) {
    vector<vector<int>> dp(coins.size(), vector<int>(sum+1, 0));
    
    for (int i=coins.size()-1; i>=0; i--) {
        for (int j=1; j<=sum; j++) {
            dp[i][j] = INT_MAX;
            int take = INT_MAX, noTake = INT_MAX;
            
            // If we take coins[i] coin
            if (j-coins[i]>=0) {
                take = dp[i][j-coins[i]];
                if (take != INT_MAX) take++;
            }
            
            if (i+1<coins.size())
            // not take the coin 
                noTake = dp[i+1][j];
            
            dp[i][j] = min(take, noTake);
        }
    }
    
    if (dp[0][sum]!=INT_MAX) return dp[0][sum];
    return -1;
}

int main() {
    vector<int> coins =  {9, 6, 5, 1};
    int sum = 19;
    cout << minCoins(coins, sum);
    return 0;
}

Java

// Java program to find minimum of coins
// to make a given change sum

import java.util.Arrays;

class GfG {

    static int minCoins(int[] coins, int sum) {
        int[][] dp = new int[coins.length][sum + 1];

        for (int i = coins.length - 1; i >= 0; i--) {
            for (int j = 1; j <= sum; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                int take = Integer.MAX_VALUE, noTake = Integer.MAX_VALUE;

                // If we take coins[i] coin
                if (j - coins[i] >= 0) {
                    take = dp[i][j - coins[i]];
                    if (take != Integer.MAX_VALUE) take++;
                }
                  // not take the coin 
                if (i + 1 < coins.length) noTake = dp[i + 1][j];

                dp[i][j] = Math.min(take, noTake);
            }
        }

        if (dp[0][sum] != Integer.MAX_VALUE) return dp[0][sum];
        return -1;
    }

    public static void main(String[] args) {
        int[] coins = {9, 6, 5, 1};
        int sum = 19;
        System.out.println(minCoins(coins, sum));
    }
}

Python

# Python program to find minimum of coins
# to make a given change sum

def minCoins(coins, sum):
    dp = [[0] * (sum + 1) for _ in range(len(coins))]

    for i in range(len(coins) - 1, -1, -1):
        for j in range(1, sum + 1):
            dp[i][j] = float('inf')
            take = float('inf')
            noTake = float('inf')

            # If we take coins[i] coin
            if j - coins[i] >= 0:
                take = dp[i][j - coins[i]]
                if take != float('inf'):
                    take += 1

            if i + 1 < len(coins):
                #not take the coins
                noTake = dp[i + 1][j]

            dp[i][j] = min(take, noTake)

    if dp[0][sum] != float('inf'):
        return dp[0][sum]
    return -1

if __name__ == "__main__":
    coins = [9, 6, 5, 1]
    sum = 19
    print(minCoins(coins, sum))

C#

// C# program to find minimum of coins
// to make a given change sum

using System;

class GfG {

    static int minCoins(int[] coins, int sum) {
        int[,] dp = new int[coins.Length, sum + 1];

        for (int i = coins.Length - 1; i >= 0; i--) {
            for (int j = 1; j <= sum; j++) {
                dp[i, j] = int.MaxValue;
                int take = int.MaxValue, noTake = int.MaxValue;

                // If we take coins[i] coin
                if (j - coins[i] >= 0) {
                    take = dp[i, j - coins[i]];
                    if (take != int.MaxValue) take++;
                }

                if (i + 1 < coins.Length) 
                // not take the coins 
                noTake = dp[i + 1, j];

                dp[i, j] = Math.Min(take, noTake);
            }
        }

        if (dp[0, sum] != int.MaxValue) return dp[0, sum];
        return -1;
    }

    static void Main(string[] args) {
        int[] coins = { 9, 6, 5, 1 };
        int sum = 19;
        Console.WriteLine(minCoins(coins, sum));
    }
}

JavaScript

// JavaScript program to find minimum of coins
// to make a given change sum

function minCoins(coins, sum) {
    let dp = Array.from({ length: coins.length }, () => Array(sum + 1).fill(0));

    for (let i = coins.length - 1; i >= 0; i--) {
        for (let j = 1; j <= sum; j++) {
            dp[i][j] = Number.MAX_VALUE;
            let take = Number.MAX_VALUE, noTake = Number.MAX_VALUE;

            // If we take coins[i] coin
            if (j - coins[i] >= 0) {
                take = dp[i][j - coins[i]];
                if (take !== Number.MAX_VALUE) take++;
            }

            if (i + 1 < coins.length)
            // not take the coins 
            noTake = dp[i + 1][j];

            dp[i][j] = Math.min(take, noTake);
        }
    }

    if (dp[0][sum] !== Number.MAX_VALUE) return dp[0][sum];
    return -1;
}

// Driver code
const coins = [9, 6, 5, 1];
const sum = 19;
console.log(minCoins(coins, sum));

Output

[Expected Approach] Using Space Optimized DP – O(n*sum) Time and O(sum) Space

In previous approach of dynamic programming we have derive the relation between states as given below:
if (sum-coins[i]) is greater than 0, then dp[i][sum] = min(1+dp[i][sum-coins[i]], dp[i+1][sum])
else dp[i][sum] = dp[i+1][sum].
If we observe that for calculating current dp[i][sum] state we only need previous row dp[i-1][sum] or current row dp[i][sum-coins[i]]. There is no need to store all the previous states just one previous state is used to compute result.

C++

// C++ program to find minimum of coins
// to make a given change sum
#include<bits/stdc++.h>
using namespace std;

// Function to find the minimum number of 
// coins needed to make the given sum
int minCoins(vector<int> &coins, int sum) {
    
    // Create a DP array to store the minimum coins
    // for each value up to sum
    vector<int> dp(sum+1, INT_MAX);
    
    // Base case: 0 coins are needed to make sum 0
    dp[0] = 0; 
    
    // Iterate over each coin in the coins array
    for (int i=coins.size()-1; i>=0; i--) {
        
        // Iterate through all sums from 1 to the given sum
        for (int j=1; j<=sum; j++) {
            
            // Initialize take and noTake variables
            int take = INT_MAX, noTake = INT_MAX;
            
            // Check if we can take the current coin
            if (j-coins[i]>=0 && coins[i]>0) {
                
                // Get the minimum coins needed for
                // the remaining sum
                take = dp[j-coins[i]]; 
                
                // Increment take if it's a valid option
                if (take != INT_MAX) take++; 
            }
            
            // If we have more coins available,
            // consider not taking the current coin
            
            if (i+1<coins.size())
            // Get the minimum coins needed without
            // taking the current coi
                noTake = dp[j]; 
            
            // Update the DP array with the minimum of
            // taking or not taking the coin
            dp[j] = min(take, noTake);
        }
    }
    
    // found a solution, return the minimum
    // coins needed, otherwise return -1
    if (dp[sum]!=INT_MAX) return dp[sum];
    return -1;
}

int main() {
    vector<int> coins =  {9, 6, 5, 1};
    int sum = 19; 
    cout << minCoins(coins, sum);
    return 0;
}

Java

// Java program to find minimum of coins
import java.util.Arrays;

 class GfG {
    
    // Function to find the minimum number 
    // of coins required to make a given sum
     static int minCoins(int[] coins, int sum) {
         
        // Array to store the minimum coins needed for
        // each value up to sum
        int[] dp = new int[sum + 1];
        
        // Initialize the dp array with a large value (infinity)
        Arrays.fill(dp, Integer.MAX_VALUE);
        
        // Base case: 0 coins are needed to make the sum of 0
        dp[0] = 0;
        
        // Iterate through each coin in reverse order
        for (int i = coins.length - 1; i >= 0; i--) {
            
            // Iterate through all sums from 1 to the target sum
            for (int j = 1; j <= sum; j++) {
                
                // Initialize variables to track taking 
                // or not taking the coin
                int take = Integer.MAX_VALUE, noTake = Integer.MAX_VALUE;
                
                // If we can take the current coin
                if (j - coins[i] >= 0 && coins[i] > 0) {
                    take = dp[j - coins[i]];
                    
                    // If taking the coin is possible,
                    // increment the count
                    if (take != Integer.MAX_VALUE) take++;
                }
                
                // If there are more coins available,
                // consider not taking the current coin
                if (i + 1 < coins.length)
                    noTake = dp[j];
                
                // Store the minimum of taking or 
                // not taking the coin
                dp[j] = Math.min(take, noTake);
            }
        }
        
        // Return the minimum coins needed for 
        // the target sum, or -1 if not possible
        return dp[sum] != Integer.MAX_VALUE ? dp[sum] : -1;
    }

    public static void main(String[] args) {
        int[] coins = {9, 6, 5, 1};
        int sum = 19;
        System.out.println(minCoins(coins, sum));
    }
}

Python

# Python program to find minimum of coins
def minCoins(coins, sum):
    
    # Initialize a list to store the minimum 
    # number of coins for each amount
    dp = [float('inf')] * (sum + 1)
    
    # Base case: 0 coins are needed to make the sum of 0
    dp[0] = 0 
    
    # Iterate over each coin in reverse order
    for i in range(len(coins) - 1, -1, -1):
        
        # Iterate through all amounts from 1 to sum
        for j in range(1, sum + 1):
            
            #  take variable for the current coin
            take = float('inf')  
            
            #  noTake variable for the current amount
            noTake = float('inf') 
            
            # If we can take the current coin
            if j - coins[i] >= 0 and coins[i] > 0:
                
                # Get the minimum coins needed 
                # for the remaining amount
                take = dp[j - coins[i]]
                
                # Increment the count if it's a valid take
                if take != float('inf'): 
                    take += 1
            
            # If there are coins left to consider
            if i + 1 < len(coins):
                
                # Get the minimum coins needed without
                # taking the current coin
                noTake = dp[j] 
                
            # Store the minimum of taking or not
            # taking the current coin
            dp[j] = min(take, noTake)
    
    # Return the result for the given sum,
    # or -1 if it's not possible
    return dp[sum] if dp[sum] != float('inf') else -1

if __name__ == "__main__":
    coins = [9, 6, 5, 1]
    sum = 19 
    print(minCoins(coins, sum))

C#

// C# program to find minimum of coins
using System;
using System.Linq;

class GfG {
    
    // Function to find the minimum number of 
    // coins required to make a given sum
     static int minCoinsFunc(int[] coins, int sum) {
        
        // Create a DP array initialized to maximum value
        int[] dp = Enumerable.Repeat(int.MaxValue, sum + 1).ToArray();
        dp[0] = 0; 
        
        // Iterate through each coin
        for (int i = coins.Length - 1; i >= 0; i--) {
            
            // Iterate through all sums from 1 to the target sum
            for (int j = 1; j <= sum; j++) {
                int take = int.MaxValue, noTake = int.MaxValue;
                
                // If we take coins[i] coin
                if (j - coins[i] >= 0 && coins[i] > 0) {
                    
                    // Get the value if we take this coin
                    take = dp[j - coins[i]];
                    
                    // Increment the coin count
                    if (take != int.MaxValue) take++;
                }
                
                // Get the value if we do not take this coin
                if (i + 1 < coins.Length)
                    noTake = dp[j];
                    
                // Store the minimum of taking or not taking the coin
                dp[j] = Math.Min(take, noTake);
            }
        }
        
        // Return the result: if no combination found, return -1
        return dp[sum] != int.MaxValue ? dp[sum] : -1;
    }
    // Main function to test the MinCoinsFunc
    public static void Main() {
        int[] coins = {9, 6, 5, 1};
        int sum = 19;
        Console.WriteLine(minCoinsFunc(coins, sum));
    }
}

JavaScript

// JavaScript program to find minimum of coins
function minCoins(coins, sum) {
    
    // Initialize an array to store the 
    // minimum coins needed for each amount
    let dp = new Array(sum + 1).fill(Infinity);
    dp[0] = 0;
    
    // Iterate through each coin in the coins array
    for (let i = coins.length - 1; i >= 0; i--) {
        
        // Iterate through all sums from 1
        // to the target sum
        for (let j = 1; j <= sum; j++) {
            
            // Initialize take and noTake variables
            let take = Infinity, noTake = Infinity;
            
            // If we can take the current coin
            if (j - coins[i] >= 0 && coins[i] > 0) {
                
                // Get the minimum coins for the remaining sum
                take = dp[j - coins[i]];
                
                // Increment the coins count if valid
                if (take !== Infinity) take++; 
            }
            // If not taking the current coin, 
            // just take the previous value
            if (i + 1 < coins.length)
                noTake = dp[j];
                
            // Store the minimum of taking or not taking the coin
            dp[j] = Math.min(take, noTake);
        }
    }
    // Return the result for the target sum,
    // or -1 if it's not possible
    return dp[sum] !== Infinity ? dp[sum] : -1;
}

// Driver code 
let coins = [9, 6, 5, 1]; 
let sum = 19; 
console.log(minCoins(coins, sum));

Output

Coin Change - Minimum Coins to Make Sum

explore course icon

K

Improve

Article Tags :

Explore