Min Coins to Make Change - Backtracking / Aggregation and Memoization

https://algo.monster/problems/coin-change-backtracking

Using dedup

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

    if remaining == 0:
        res.append(path[:])
        return

    for i in range(start, n):
        coin = coins[i]
        if remaining - coin < 0:
            continue
        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
2

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:
            continue
        ans = min(res+1, inf)
    

    memo[sum]=ans
    
    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)
  console.log(count);


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

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

It’s wrong approach guys

sorry

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:
            continue
        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
else:
    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) {
                    continue;
                }
                min = Math.min(min,res + 1);
            }
        }
        memo[amount] = min;
        return min;
    }