Problem Statement:
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.
Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Example 3:
Input: coins = [1], amount = 0
Output: 0
Constraints
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
Approach:
- Use recursion (fn(remAmount)) to try reducing the amount by picking each coin.
- Base cases:
- If
remAmount == 0, no coins are needed → return0. - If
remAmount < 0, invalid case → return-1.
- If
- Store already-computed results in a memo
(dp)to avoid re-computation. -
For each coin, recursively compute the minimum coins needed for
remAmount - coin.- If result is valid
(!= -1), update the minimum.
- If result is valid
- Save the best result in
dp[remAmount]. - Final answer is
fn(amount)→ the minimum number of coins or-1if impossible.
Time & Space Complexity:
Time Complexity: O(amount x n)
Space Complexity: O(amount)
Dry Run
Input: coins = [1, 2, 5], amount = 11
Step 0: Start Function: coinChange([1,2,5], 11)
n = 3
dp = {}
Call fn(11):
fn(11):
- remAmount = 11 (not in dp, >0)
- minCoins = Infinity
Try coin = 1 → call fn(10)
Try coin = 2 → call fn(9)
Try coin = 5 → call fn(6)
fn(10):
- remAmount = 10
- minCoins = Infinity
coin = 1 → fn(9)
coin = 2 → fn(8)
coin = 5 → fn(5)
fn(9):
- remAmount = 9
- minCoins = Infinity
coin = 1 → fn(8)
coin = 2 → fn(7)
coin = 5 → fn(4)
fn(8):
- remAmount = 8
- minCoins = Infinity
coin = 1 → fn(7)
coin = 2 → fn(6)
coin = 5 → fn(3)
fn(7):
- remAmount = 7
- minCoins = Infinity
coin = 1 → fn(6)
coin = 2 → fn(5)
coin = 5 → fn(2)
fn(6):
- remAmount = 6
- minCoins = Infinity
coin = 1 → fn(5)
coin = 2 → fn(4)
coin = 5 → fn(1)
fn(5):
- remAmount = 5
- minCoins = Infinity
coin = 1 → fn(4)
coin = 2 → fn(3)
coin = 5 → fn(0)
fn(0) = 0 (base case)
So fn(5) = min(1 + fn(0)) = 1
dp[5] = 1
fn(6):
- got fn(5) = 1
- Try coin=5 → fn(1)
fn(1):
- remAmount = 1
- Try coin=1 → fn(0) = 0
- minCoins = 1
dp[1] = 1
So fn(6) = min( fn(5)+1 , fn(4)+1, fn(1)+1 )
= min(2, ?, 2) = 2
dp[6] = 2
fn(7):
- Try coin=2 → fn(5)=1
- Try coin=5 → fn(2)
fn(2):
- remAmount = 2
- coin=1 → fn(1)=1 → total=2
- coin=2 → fn(0)=0 → total=1
dp[2] = 1
So fn(7) = min( fn(6)+1=3, fn(5)+1=2, fn(2)+1=2 ) = 2
dp[7] = 2
fn(8):
- Try coin=2 → fn(6)=2 → total=3
- Try coin=5 → fn(3)
fn(3):
- remAmount = 3
- coin=1 → fn(2)=1 → total=2
- coin=2 → fn(1)=1 → total=2
- coin=5 → fn(-2) = -1 (ignore)
dp[3] = 2
So fn(8) = min( fn(7)+1=3, fn(6)+1=3, fn(3)+1=3 ) = 3
dp[8] = 3
fn(9):
- Try coin=2 → fn(7)=2 → total=3
- Try coin=5 → fn(4)
fn(4):
- remAmount = 4
- coin=1 → fn(3)=2 → total=3
- coin=2 → fn(2)=1 → total=2
- coin=5 → fn(-1) = -1
dp[4] = 2
So fn(9) = min( fn(8)+1=4, fn(7)+1=3, fn(4)+1=3 ) = 3
dp[9] = 3
fn(10):
- Try coin=1 → fn(9)=3 → total=4
- Try coin=2 → fn(8)=3 → total=4
- Try coin=5 → fn(5)=1 → total=2
dp[10] = 2
fn(11):
- Try coin=1 → fn(10)=2 → total=3
- Try coin=2 → fn(9)=3 → total=4
- Try coin=5 → fn(6)=2 → total=3
dp[11] = 3
Step 3: End
Return dp[11] = 3
Output: 3
Visualisation:
var coinChange = function(coins, amount) {
let n = coins.length;
let dp = {};
let fn = (remAmount) => {
if (remAmount === 0) return 0;
if (remAmount < 0) return -1;
if (remAmount in dp) {
return dp[remAmount];
}
let minCoins = Infinity;
for (let i = 0; i < n; i++) {
let res = fn(remAmount - coins[i]);
if (res != -1) {
minCoins = Math.min(minCoins, 1 + res);
}
}
dp[remAmount] = (minCoins === Infinity) ? -1 : minCoins;
return dp[remAmount];
};
return fn(amount);
};
from functools import lru_cache
def coinChange(coins, amount):
@lru_cache(None)
def dfs(rem):
if rem == 0:
return 0
if rem < 0:
return -1
min_coins = float('inf')
for c in coins:
res = dfs(rem - c)
if res != -1:
min_coins = min(min_coins, 1 + res)
return -1 if min_coins == float('inf') else min_coins
return dfs(amount)
import java.util.Arrays;
class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
int[] memo = new int[amount + 1];
Arrays.fill(memo, Integer.MIN_VALUE); // sentinel for unknown
return dfs(coins, amount, memo);
}
private int dfs(int[] coins, int rem, int[] memo) {
if (rem == 0) return 0;
if (rem < 0) return -1;
if (memo[rem] != Integer.MIN_VALUE) return memo[rem];
int minCoins = Integer.MAX_VALUE;
for (int c : coins) {
int res = dfs(coins, rem - c, memo);
if (res != -1) minCoins = Math.min(minCoins, 1 + res);
}
memo[rem] = (minCoins == Integer.MAX_VALUE) ? -1 : minCoins;
return memo[rem];
}
}
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int coinChange(vector& coins, int amount) {
if (amount == 0) return 0;
int n = coins.size();
vector memo(amount + 1, INT_MIN); // sentinel = unknown
function dfs = [&](int rem) -> int {
if (rem == 0) return 0;
if (rem < 0) return -1;
if (memo[rem] != INT_MIN) return memo[rem];
int minCoins = INT_MAX;
for (int i = 0; i < n; ++i) {
int res = dfs(rem - coins[i]);
if (res != -1) minCoins = min(minCoins, 1 + res);
}
memo[rem] = (minCoins == INT_MAX) ? -1 : minCoins;
return memo[rem];
};
return dfs(amount);
}
};
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int dfs(int rem, int *coins, int n, int *memo) {
if (rem == 0) return 0;
if (rem < 0) return -1;
if (memo[rem] != INT_MIN) return memo[rem];
int minCoins = INT_MAX;
for (int i = 0; i < n; ++i) {
int res = dfs(rem - coins[i], coins, n, memo);
if (res != -1 && res + 1 < minCoins) minCoins = res + 1;
}
memo[rem] = (minCoins == INT_MAX) ? -1 : minCoins;
return memo[rem];
}
int coinChange(int *coins, int n, int amount) {
if (amount == 0) return 0;
int *memo = (int*)malloc((amount + 1) * sizeof(int));
if (!memo) return -1; // allocation failure fallback
for (int i = 0; i <= amount; ++i) memo[i] = INT_MIN;
int ans = dfs(amount, coins, n, memo);
free(memo);
return ans;
}
using System;
public class Solution {
public int CoinChange(int[] coins, int amount) {
if (amount == 0) return 0;
int n = coins.Length;
int[] memo = new int[amount + 1];
for (int i = 0; i <= amount; i++) memo[i] = int.MinValue; // sentinel for "unknown"
int DFS(int rem) {
if (rem == 0) return 0;
if (rem < 0) return -1;
if (memo[rem] != int.MinValue) return memo[rem];
int minCoins = int.MaxValue;
for (int i = 0; i < n; i++) {
int res = DFS(rem - coins[i]);
if (res != -1) minCoins = Math.Min(minCoins, 1 + res);
}
memo[rem] = (minCoins == int.MaxValue) ? -1 : minCoins;
return memo[rem];
}
return DFS(amount);
}
}
