# Min Coins to Make Change - Backtracking / Aggregation and Memoization

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?

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 existing`ans`

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;
}
``````

My solution is more similar to our template in aggregation.

``````def coin_change(coins: List[int], amount: int) -> int:
# WRITE YOUR BRILLIANT CODE HERE
def dfs(left, steps):
if left == 0:
return steps
ans = float("Inf")
for c in coins:
if left < 0:
continue
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.

Why?
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
``````