Min Coins to Make Change - Backtracking / Aggregation and Memoization


Using dedup

def dfs(coins, start, remaining, path):
    n = len(coins)

    if remaining == 0:

    for i in range(start, n):
        coin = coins[i]
        if remaining - coin < 0:
        dfs(coins, i, remaining - coin, path + [coin])
res = []
dfs(coins, 0, amount, [])
return len(sorted(res, key=len)[0]) if res else -1

Assuming we can sort the coins:

def coin_change(coins: List[int], amount: int) -> int:
    result = 0
    for coin in reversed(sorted(coins)):
        result += amount // coin
        amount = amount % coin

    return result if amount == 0 else -1

this is greedy algorithm and does not work for all the cases

This code is not working for this input

1 2147483647

Can someone help.

I’m doing memoization with a dictionary like this:

def coin_change(coins: List[int], amount: int) → int:
memo = {}
def min_coins(coins, amount, sum):
if sum == amount:
return 0

    if sum > amount:
        return inf
    if sum in memo:
        return memo[sum]
    ans = inf
    for coin in coins:
        res = min_coins(coins, amount, sum+coin)
        if res == inf:
        ans = min(res+1, inf)

    return ans
result = min_coins(coins, amount, 0)
return -1 if result == inf else result

but it’s not producing correct result for last case. any idea why?
Thanks in advance.

a far superior way of solving

const coinChange = (coins, amount) => {
const cl = coins.length;//length of the coins array

coins.sort((a, b) => b - a);

let count = 0;

const resMap = new Map(); //For Memoization

//sum: Sum made till date,index:index of symbol array ,l:level
const dfs = (sum, index, l) => {

count += 1;

if (sum === amount)
  return 0;

else if (resMap.has(sum))
  return resMap.get(sum);

let ans = -1;

for (let i = index; i < cl; i += 1) {
  if (sum + coins[i] <= amount) {
    const tans = dfs(sum + coins[i], i, l + 1);

    if (tans !== -1 && ans !== -1)
      ans = Math.min(ans, tans);
    else if (tans !== -1 && ans === -1)
      ans = tans;

if (l === 0)

if (ans !== -1) {
  resMap.set(sum, ans + 1);
  return ans + 1;
resMap.set(sum, ans);
return ans;


return dfs(0, 0, 0);

you can check it by difference in count (how many number of times dfs function calls) value

186 419 83 408
Count = 17501 (For given solution) Count = 5814 (for my solution)

It’s wrong approach guys


ans = min(res+1, inf) should be ans = min(res+1, ans) cuz you want to compare with the existingans

Dear Moderator(s),

I approached this problem slightly differently. Instead of using sum, I pass remaining balance as a function argument (amount-coin). Initially, my balance is the amount itself. My DFS returns the minimum number of coins, which is also passed to it as a function argument. In each subsequent recursive call, I increment the min coins by 1. The base case is when the balance is zero, and I return the min coins function argument itself as my answer, because there are no more coins to add.

The code works for all test cases and as expected, times out for larger inputs. My question is what do I memo on? I intuitively used memo on the balance, but it doesn’t seem to work for all test cases. It only works for scenarios where the amount equals one of the coins in the list of coins. Why is this happening? Can you explain, what can I memo, in this approach?

Is this question same as the one in DP section?

Yes, it’s the same. you can solve it with bottom up dp too.

I approached the same way and found a memo approach that works

def coin_change(coins: List[int], amount: int) → int:
memo = {}

def impl(num_coins: int, amt_left: int) -> int:
    if amt_left in memo:
        return memo[amt_left] + num_coins
    if amt_left == 0:
        return num_coins

    run_min = inf
    for coin in coins:
        if amt_left - coin < 0:
        tmp_num_coins = impl(num_coins + 1, amt_left - coin)
        run_min = min(tmp_num_coins, run_min)
    memo[amt_left] = run_min - num_coins
    return run_min

ans = impl(0, amount)
if ans == inf:
    return -1
    return ans

How would we find the list of coins used along with the minimum number of coins with this logic?

Memoization template Solution with a little bit of brevity

def coin_change(coins: List[int], amount: int) → int:
memo = [-1] * amount
def dfs(current_sum):
if current_sum == amount:
return 0
if current_sum > amount:
return inf
if memo[current_sum] != -1:
return memo[current_sum]

    min_coin = inf
    for coin in coins:
        result = dfs(current_sum + coin)
        if result != inf:
            min_coin = min(min_coin, result + 1)
    memo[current_sum] = min_coin
    return min_coin

result = dfs(0)
return result if result != inf else -1

Tracking the difference instead of sum
Key note:
Memorization of amount instead of sum

    private static int dfs(List<Integer> coins, int amount, int[] memo) {
        if (amount == 0) {
            return 0;
        if (memo[amount] != -1) { 
            return memo[amount]; 
        int min = Integer.MAX_VALUE;
        for (int c : coins) {
            if (amount - c >= 0) { // This guard can be factored out
                int res = dfs(coins, amount - c, memo);
                if (res == Integer.MAX_VALUE) {
                min = Math.min(min,res + 1);
        memo[amount] = min;
        return min;

My solution is more similar to our template in aggregation.

def coin_change(coins: List[int], amount: int) -> int:
    def dfs(left, steps):
        if left == 0:
            return steps 
        ans = float("Inf")
        for c in coins:
            if left < 0:
            res = dfs(left-c, steps+1)
            ans = min(ans, res)
        return ans
    out = dfs(amount, 0)
    if out == float("Inf"):
        return -1
    return out

Agree to people above, leftover amount approach is easier to understand and implement and it also better correlates with what we learned before

The solution still works, however we need to initiate an Integer array instead of int array.

coz Integer array is null by default,

Using DP’s concept to do dfs

def coin_change(coins: List[int], amount: int) -> int:
    def dfs(remained_amount, mem={}):
        if remained_amount in mem:
            return mem[remained_amount]
        if remained_amount == 0:
            return 0
        if remained_amount < 0:
            return float("inf")

        min_nums = float("inf")
        for coin in coins:
            min_nums = min(min_nums, dfs(remained_amount - coin) + 1)
        mem[remained_amount] = min_nums
        return min_nums
    min_nums = dfs(amount)
    return -1 if min_nums == float("inf") else min_nums