Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Examples

Example 1:

1
2
3

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

1
2
3
4
5

Input: coins = [1,2,3], amount = 5
Output: 2
Explanation: 5 = 2+3
No of ways to make the change are : { 1,1,1,1,1} , {1,1,1,2}, {2,2,1},{1,1,3} and {3,2}.
So as we can see minimum number of coins required are 2 ( 3+2=5}.

Note

There is another simpler version or variant of the problem Coin Change with Fewest Number of Coins Given Canonical System and Infinite Supply. We will solve generic case here, but the canonical system is easier to solve with greedy approach.

Solution

For every coin, we have two choices: either to include it or exclude it. Thus, we can evaluate both scenarios and select the optimal solution, which in this context is the minimum among all possible solutions.

To solve this, we first decompose the problem into smaller subproblems. But what exactly are these subproblems?

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Recursion

Let’s say we have a set of 3 coins: {1, 2, 5}, representing denominations of one unit, two units, and five units respectively. To find the solution, we need to determine which of the following is the minimum: using a coin of denomination 1 plus the number of coins required for the remaining amount after subtracting 1, using a coin of denomination 2 plus the number of coins required for the remaining amount after subtracting 2, or using a coin of denomination 5 plus the number of coins required for the remaining amount after subtracting 5.

The number of coins needed for the original amount is thus calculated as follows:

$$ numCoins = \begin{cases} 1 + numCoins(originalAmount - 1) \\ 1 + numCoins(originalAmount - 2) \\ 1 + numCoins(originalAmount - 5) \\ \end{cases} $$

However, this algorithm is highly inefficient. For instance, if we need to make change for 7 cents (A = 7), the recursion tree would appear as follows:

graph TD
    A(7) -->|1| B(6)
    A -->|2| C(5):::yellow
    A -->|5| D(2)

    B -->|1| E(5):::yellow
    B -->|2| F(4)
    B -->|5| G(1)

    C -->|1| H(4)
    C -->|2| I(3)
    C -->|5| J(0):::green

    D -->|1| K(1)
    D -->|2| L(0):::green
    D -->|5| M("-3"):::red

    E --> Incomplete1["..."]
    
    F -->|1| N(3)
    F -->|2| O(2)
    F -->|5| P("-1"):::red

    H -->|1| Q(2)
    H -->|2| R(1)
    H -->|5| S("-2"):::red

    G -->|1| T(0):::green
    G -->|2| U("-1"):::red
    G -->|5| V("-4"):::red

	 K -->|1| W(0):::green
    K -->|2| X("-1"):::red
    K -->|5| Y("-4"):::red

    N --> Incomplete5["..."]
    O --> Incomplete6["..."]
    Q --> Incomplete7["..."]
    R --> Incomplete8["..."]

classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff; 
classDef red fill:#FF0000,stroke:#000,stroke-width:1px,color:#fff; 
style Incomplete1 display:none
style Incomplete5 display:none
style Incomplete6 display:none
style Incomplete7 display:none
style Incomplete8 display:none
classDef yellow fill:#FFD700,stroke:#000,stroke-width:1px,color:#000;

In the image we can see that tree is expanding at least 2 times from 5 itself, so that is really inefficient. But we also have repeating subproblems for 4, 3, 2, 1 etc.

The time complexity of above solution is exponential. Every coin has 2 options, to be selected or not selected.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {

    public int coinChange(int[] coins, int amount) {
        // Call the recursive function
        int ans = helper(coins, amount);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    private int helper(int[] coins, int remaining) {
        // Base cases
        if (remaining == 0) return 0; // No coins needed for amount 0
        if (remaining < 0) return Integer.MAX_VALUE; // Invalid case

        int minCoins = Integer.MAX_VALUE;

        // Try all possible coins and compute the minimum number of coins needed
        for (int c : coins) {
            int res = helper(coins, remaining - c);
            if (res != Integer.MAX_VALUE) {
                minCoins = Math.min(minCoins, res + 1); // Add 1 to account for current coin usage
            }
        }

        return minCoins;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        def helper(remaining: int) -> int:
            # Base cases
            if remaining == 0:
                return 0  # No coins needed for amount 0
            if remaining < 0:
                return float('inf')  # Invalid case
            
            # Try all coins and find the minimum number of coins needed
            min_coins = float('inf')
            for c in coins:
                res = helper(remaining - c)
                if res != float('inf'):
                    min_coins = min(min_coins, res + 1)  # Add 1 for current coin usage
            
            return min_coins
        
        # Call the recursive helper function
        ans = helper(amount)
        return -1 if ans == float('inf') else int(ans)

Complexity

  • ⏰ Time complexity: O(n^A) where n is number of coins and A is the amount. The recursion tree depth is equal to the A (the target amount). This is because we reduce the amount step by step until it reaches 0 or becomes negative. At each level of recursion, we have n branches (one for each coin denomination).
  • 🧺 Space complexity: O(A). The maximum recursion depth is equal to A (in the worst-case scenario where the coin denomination is 1, requiring A recursive calls to reduce the amount to 0).

Method 2 - Top Down DP

To improve the efficiency, we use memoization to store the results of subproblems that have already been computed. This helps avoid re-computation and reduces the time complexity.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    public int coinChange(int[] coins, int amount) {
        // Memoisation map to store the results of subproblems
        Map<Integer, Integer> memo = new HashMap<>();

        // Helper method for recursion and memoisation
        int helper(int remaining) {
            // Base cases
            if (remaining == 0) return 0; // No coins needed for amount = 0
            if (remaining < 0) return Integer.MAX_VALUE; // Invalid case, return infinity

            // If the result for this amount is already computed, return it
            if (memo.containsKey(remaining)) return memo.get(remaining);

            // Compute the minimum coins needed for the current amount
            int minCoins = Integer.MAX_VALUE;
            for (int coin : coins) {
                int res = helper(remaining - coin);
                if (res != Integer.MAX_VALUE) {
                    minCoins = Math.min(minCoins, res + 1); // Add 1 for using the current coin
                }
            }

            // Store the computed result in the memoisation map
            memo.put(remaining, minCoins);
            return minCoins;
        }

        // Solve for the given amount starting from the top
        int ans = helper(amount);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # Memoisation table to store the results of subproblems
        memo = {}

        def helper(remaining: int) -> int:
            # Base cases
            if remaining == 0:
                return 0  # No coins needed for amount = 0
            if remaining < 0:
                return float('inf')  # Invalid case, return infinity

            # If the result for this amount is already computed, return it
            if remaining in memo:
                return memo[remaining]

            # Compute the minimum coins needed for the current amount
            min_coins = float('inf')
            for coin in coins:
                res = helper(remaining - coin)
                if res != float('inf'):
                    min_coins = min(min_coins, res + 1)  # Add 1 for using the current coin

            # Store the computed result in the memoisation table
            memo[remaining] = min_coins
            return min_coins

        # Solve for the given amount starting from the top
        ans = helper(amount)
        return -1 if ans == float('inf') else ans

Complexity

  • ⏰ Time complexity: O(A*n)
    • Each amount from 0 to A (where A is the target amount) is solved only once.
    • For each amount, we iterate through n coins.
    • Thus, the time complexity is O(A * n).
  • 🧺 Space complexity: O(A)
    • Space for the memoisation table is O(A) (since amounts are stored from 0 to A).
    • Recursive call stack depth is at most O(A) (in the worst case).

Method 3 - Bottom up DP

Let’s see how we can apply dynamic programming (DP) to solve this problem effectively.

1. Optimal Substructure

Given coin denominations coins[] and the target amount A, we recognize that we can build the solution using the substructure property. Here’s a revised view:

1
2
3
4
5
6
7

minCoins(coins[], A) =
	Base conditions:
	if (A == 0)         => 0
	if (A < 0)          => Integer.MAX_VALUE
 
	Recurrence relation:
	min(minCoins(coins, A - coins[i]) + 1) for all coins[i] such that coins[i] <= A

2. Overlapping Subproblems

With a naive recursive implementation, we would repeatedly calculate the same subproblems which is inefficient. Here’s how we can use dynamic programming:

1
2
3
4

for all i from 0 to amount:
	for all coin in coins:
		if (i - coin >= 0)
			dp[i] = min(dp[i], dp[i - coin] + 1)
  • dp[i] represents the minimum number of coins needed to make the amount i.
  • For each coin, if we include the coin in the solution, we add 1 to the result of dp[i - coin].

Detailed Steps

  • We maintain an array dp[] where dp[i] represents the minimum number of coins needed for the amount i.
  • Initialize dp[] with a high value (e.g., Integer.MAX_VALUE) and set dp[0] to 0 since no coins are required to make an amount of 0.
  • Using a bottom-up approach, we fill out the array dp[] for all values from 0 to amount.
  • The final solution will be in dp[amount] which will give us the minimum number of coins required to make the amount n. If it remains as Integer.MAX_VALUE, it means the target amount cannot be made with the given denominations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
      public int coinChange(int[] coins, int amount) {
            // Create a DP array to store the minimum coins required for each amount
            int[] dp = new int[amount + 1];
            Arrays.fill(dp, amount + 1); // Treat 'amount + 1' as infinity
            dp[0] = 0; // Base case: no coins needed for amount = 0

            // Build the DP array iteratively
            for (int i = 1; i <= amount; i++) {
                  for (int c : coins) {
                        if (i >= c) { // Check if this coin can contribute to amount 'i'
                              dp[i] = Math.min(dp[i], dp[i - c] + 1);
                        }
                  }
            }

            // Final result: if dp[amount] is still 'amount + 1', it means no valid solution
            return dp[amount] == amount + 1 ? -1 : dp[amount];
      }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
      def coinChange(self, coins: List[int], amount: int) -> int:
            # Create a DP array to store the minimum coins required for each amount
            dp = [amount + 1] * (amount + 1)  # Treat 'amount + 1' as infinity
            dp[0] = 0  # Base case: no coins needed for amount = 0

            # Build the DP array iteratively
            for i in range(1, amount + 1):
                  for c in coins:
                        if i >= c:  # Check if this coin can contribute to amount 'i'
                              dp[i] = min(dp[i], dp[i - c] + 1)

            # Final result: if dp[amount] is still 'amount + 1', it means no valid solution
            return -1 if dp[amount] == amount + 1 else dp[amount]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class Solution {
    public int coinChange(int[] coins, int amount) {
        // this will store the optimal solution
        // for all the values -- from 0 to given amount.
        int[] dp = new int[amount+1];
        dp[0] = 0; // 0 coins are required to make the change for 0 (no need to set as default val is already 0 but for clarity)
        // now solve for all the amounts
        for (int a = 1; a <= amount; a++) {
            dp[a] = Integer.MAX_VALUE; // initially we don't know solution, hence ∞
            // Now try taking every coin one at a time and pick the minimum
            for (int coin: coins) {
                if (coin <= a && dp[a - coin] != Integer.MAX_VALUE) { // check if coin value is less than amount
                    // select the coin and add 1 to solution of (amount-coin value)
                    dp[a]= Math.min(dp[a], 1 + dp[a - coin]);
                }
            }
        }
        //return the optimal solution for amount
        return dp[amount] != Integer.MAX_VALUE ? dp[amount]: -1 ;

    }
}

Complexity

  • ⏰ Time complexity: O(A*n)
    • We iterate through all amounts from 1 to A (the target amount), and for each amount, we iterate through all n coin denominations.
    • Thus, the total number of steps is proportional to A * n.
  • 🧺 Space complexity: O(A), as we use a single dp array of size A + 1 to store the minimum coins required for each amount.

Dry Run

Let’s dry run the code for amount = 13 and coins = [7, 2, 3, 6] using the bottom-up dynamic programming approach.

Initial Setup
  1. Array dp[] Initialization:
    • dp[0] = 0 (0 coins to make amount 0).
    • All other dp[i] initialized to amount + 1 (infinity in this context).
Initial dp Array
1

 dp = [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
Filling dp[] Array

We iterate over each amount from 1 to 13 and for each coin.

Iteration for i = 1
  • Coin = 7: i - coin < 0, no update.
  • Coin = 2: i - coin < 0, no update.
  • Coin = 3: i - coin < 0, no update.
  • Coin = 6: i - coin < 0, no update.
1

 dp = [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
Iteration for i = 2

  • Coin = 7: i - coin < 0, no update.

  • Coin = 2: dp[2] = min(dp[2], dp[2 - 2] + 1) => dp[2] = min(inf, 0 + 1) => 1.

    1

     dp = [0, inf, 1, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]

  • Coin = 3: i - coin < 0, no update.

  • Coin = 6: i - coin < 0, no update.

Iteration for i = 3

  • Coin = 7: i - coin < 0, no update.

  • Coin = 2: No update as dp[3 - 2] + 1 continues to result in inf.

  • Coin = 3: dp[3] = min(dp[3], dp[3 - 3] + 1) => dp[3] = min(inf, 0 + 1) => 1.

    1

     dp = [0, inf, 1, 1, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]

  • Coin = 6: i - coin < 0, no update.

Iteration for i = 4

  • Coin = 7: i - coin < 0, no update.

  • Coin = 2: dp[4] = min(dp[4], dp[4 - 2] + 1) => dp[4] = min(inf, 1 + 1) => 2.

    1

     dp = [0, inf, 1, 1, 2, inf, inf, inf, inf, inf, inf, inf, inf, inf]

  • Coin = 3: dp[4] continues to be 2 after attempting to update with dp[1] + 1.

  • Coin = 6: i - coin < 0, no update.

Iteration for i = 5

  • Coin = 7: i - coin < 0, no update.

  • Coin = 2: No update as dp[5 - 2] + 1 continues to result in 2.

  • Coin = 3: dp[5] = min(dp[5], dp[5 - 3] + 1) => dp[5] = min(inf, 1 + 1) => 2.

    1

     dp = [0, inf, 1, 1, 2, 2, inf, inf, inf, inf, inf, inf, inf, inf]

  • Coin = 6: i - coin < 0, no update.

Iteration for i = 6

  • Coin = 7: i - coin < 0, no update.

  • Coin = 2: No update as dp[6 - 2] + 1 continues to be 3.

  • Coin = 3: No update as dp[6 - 3] + 1 continues to be 2.

  • Coin = 6: dp[6] = min(dp[6], dp[6 - 6] + 1) => dp[6] = min(inf, 0 + 1) => 1.

    1

     dp = [0, inf, 1, 1, 2, 2, 1, inf, inf, inf, inf, inf, inf, inf]
Iteration for i = 7

  • Coin = 7: dp[7] = min(dp[7], dp[7 - 7] + 1) => dp[7] = min(inf, 0 + 1) => 1.

    1

     dp = [0, inf, 1, 1, 2, 2, 1, 1, inf, inf, inf, inf, inf, inf]

  • Coin = 2: No update as dp[7 - 2] + 1 continues to be 3.

  • Coin = 3: No update as dp[7 - 3] + 1 continues to be 2.

  • Coin = 6: No update.

Iteration for i = 8

  • Coin = 7: No update.

  • Coin = 2: dp[8] = min(dp[8], dp[8 - 2] + 1) => dp[8] = min(inf, 1 + 1) => 2.

    1

     dp = [0, inf, 1, 1, 2, 2, 1, 1, 2, inf, inf, inf, inf, inf]

  • Coin = 3: No update as dp[8 - 3] + 1 continues to be 3.

  • Coin = 6: dp[8] = min(dp[8], dp[8 - 6] + 1) => dp[8] = min(2, 1 + 1) => 2.

Iteration for i = 9

  • Coin = 7: Update becomes higher, so no change.

  • Coin = 2: No change as dp[9 - 2] + 1 continues to be 2.

  • Coin = 3: dp[9] = min(dp[9], dp[9 - 3] + 1) => dp[9] = min(inf, 1 + 1) => 2.

  • Coin = 6: dp[9] = min(dp[9], dp[9 - 6] + 1) => dp[9] = min(dp[9], 3) => 3.

    1

     dp = [0, inf, 1, 1, 2, 2, 1, 1, 2, 2, inf, inf, inf, inf]
Iteration for i = 10

  • Coin = 7: Update becomes higher, so no change.

  • Coin = 2: No change as dp[10 - 2] + 1 is 3.

  • Coin = 3: No change as dp[10 - 3] + 1 updates it to 1.

  • Coin = 6: No change as dp[10 - 6] + 1 results the same.

    1

     dp = [0, inf, 1, 1, 2, 2, 1, 1, 2, 2, 2, inf, inf, inf]
Iteration for i = 11

  • Coin = 7: No change as adding increment results higher.

  • Coin = 2: dp[11 - 2] + 1 results the optimal list count.

  • Coin = 3: No change as adding increment results higher.

  • Coin = 6: No change as adding increment results 3.

    1

     dp = [0, inf, 1, 1, 2, 2, 1, 1, 2, 2, 3, 2, inf, inf]
Iteration for i = 12

  • Coin = 7: Update becomes higher, so no change.

  • Coin = 2: Update gets optimal value.

  • Coin = 3: No change as recursion results extra +1.

  • Coin = 6:`dp[12 -6] results the minimum.

    1

     dp = [0, inf, 1, 1, 2, 2, 1, 1, 2, 2, 3, 2, 2, inf]
Iteration for i = 13
  • Coin = 7:-update not needed as recursion count adds the extra.
  • Coin = 2: update returns optimal value as needed.
  • Coin 3: No changes required as list includes the count
  • Coin 6: Update is optional as no list recurrence added.
Final Result`

Finally, our output count returns:

1
2
3
4

  dp[13]=min(dp[13],dp[6]+1)
 `
 
 Thus dp[13] returns the minimum of 2 - {[7,6]}`

Method 4 - Using Bottom-up DP + Sorting

We can improve the speed a bit, if we sort the coins denominations:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public int minCoinsDP2Optimized( int[] coins, int amount) {
	Arrays.sort(coins); // sort the denominations
	int[] dp = new int[amount + 1]; // stores the min number of coins
	Arrays.fill(dp, amount+1); // default integer value in array is not good

	dp[0] = 0;
	for (int i = 0; i <= amount; ++i) {
		for (int j = 0; j < coins.length; j++) {
			if (coins[j] <= i) {
				dp[i] = Math.min(dp[i], 1 + dp[i - coins[j]]);
			}else {
				break; // coins array is already sorted
			}
		}
	}

	return dp[amount] > amount ? -1 : dp[amount];
}

Complexity

  • ⏰ Time complexity: O(A*n)
  • 🧺 Space complexity: O(A)

Method 5 - Using Breadth First Search

Most dynamic programming problems can also be solved using BFS.

This problem can be visualised as reaching a target position with steps taken from the array of coins. We use two queues: one to track the current amount and the other for the minimal steps taken.

Dry run with:

1

amount = 13, coins = [7, 2, 3, 6].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public int coinChange(int[] coins, int amount) {
    if (amount == 0)
        return 0;

    Queue<Integer> amountQueue = new LinkedList<Integer>();
    Queue<Integer> stepQueue = new LinkedList<Integer>();
    Set<Integer> visited = new HashSet<>(); // leveraging optimized contains using Set

    // to get 0, 0 step is required
    amountQueue.offer(0);
    stepQueue.offer(0);
    visited.add(0);

    while (amountQueue.size() > 0) {
        int currAmount = amountQueue.poll();
        int steps = stepQueue.poll();

        if (currAmount == amount) {
            return steps;        
        }

        for (int coin : coins) {
			int newAmount = currAmount + coin;
			if (newAmount <= amount && visited.add(newAmount)) {
				amountQueue.offer(newAmount);
				stepQueue.offer(steps + 1);
			}            
        }
    }

    return -1;
}

Complexity

  • ⏰ Time complexity: O(n * A)
  • 🧺 Space complexity: O(A) for storing amounts and corresponding steps in queue