Understanding a LeetCode recursion problem in Python (322 Coin Change)

Question

Leetcode Question: https://leetcode.com/problems/coin-change/

322 Coin Change:

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

Example 4:

  Input: coins = [1,4,5], amount = 8
  Output: 2
  Explanation: 8 = 4 + 4

---

So, I have been struggling with recursion and been practicing all different sorts of problems from DFS, BFS, Perms, Combos, Subsets etc, and making a little progress but not quite where I want to be for interviews.

I know this problem can be solved with DP but before moving on that concept I want to solve it using DFS to understand the problem first. I couldn't find a DFS example on the solutions.

So here is my first attempt and I keep failing some cases e.g. [186,419,83,408], 6249.

Here was my thought process for the code below.

1. The reverse is not needed I just have it there to make it faster in the debugger
2. I am going to set up a backtracking template and loop through all the indexes trying every option
3. If I match the answer I return (this might be why it's wrong since I am never popping off the total amount and there might be another option with fewer coins)
4. I keep calling backtracking trying to increment by the same coin until it doesn't work
5. if it fails I call another backtrack function incrementing the index to attempt to reach the final result

From someone more experienced: how would you have solved this problem / recognized the pattern? My original attempt was the greedy algorithm but I quickly found out that didn't work.

Maybe I should research more Top-Down bottom-up approaches but any advice on how to continue to get better or practice would be greatly appreciated. I spend a bunch of time in the debugger trying to understand these problems. I feel like giving up all the time but know that is not an option and is part of the learning curve.

def coinChange(self, coins: List[int], amount: int) -> int:
    coins = coins[::-1]
    minCoin = inf
    
    def backtrack(i,total,count):
        nonlocal minCoin
        if total == amount:
            minCoin = min(minCoin,count)
            return
        
        if total + coins[i] <= amount:
            count += 1
            backtrack(i,total + coins[i],count)
            
        if i + 1 < len(coins):
            backtrack(i+1,total,count)
        
         
    for i in range(len(coins)):
        backtrack(i,0,0)
    return minCoin if minCoin != inf else -1
        

Answer 1

I think "greedy" is the right approach. Start by assuming you need the most of the largest coin, then solve the sub-problem that is left over. If that fails, reduce the number of that largest coin and try again.

coins = [186,419,83,408]
coins.sort( reverse=1 )
tgt = 6249

def change( n, tgt, coins ):
    if not coins:
        return None
    for m in range(tgt // coins[0],-1,-1):
        tgt1 = tgt - m * coins[0]
        if not tgt1:
            print(n, m, "Answer!")
            return [m]
        chk = change( n+1, tgt1, coins[1:] )
        if chk:
            print(n, m, "Answer!")
            return [m] + chk

print(change( 0, tgt, coins ))

Output:

3 13 Answer!
2 1 Answer!
1 4 Answer!
0 8 Answer!
[8, 4, 1, 13]

Answer 2

I think your code is failing because of passing index parameter "i". The problem statement says:

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

that means if total + coins[i] <= amount you have to do a for-loop for all coins. in your code you have to start from the 0'th index but you are starting backtracking from the same index.

In recursive problems, it would be easier to be able to visualize a decision tree.

for each num in nums, you recursively make a new call for new target target-num. if you reach the leaf node, return empty array []. As you pull back to the root, add the num to the array in each level. While you make recursive call you should also be tracking the shortest path so far in memory and if you return a valid result array, compare the result with the shortest array so far and update the shortest array

from typing import List
class Solution:
    def coinChange(self, nums: List[int], target: int) -> int:
        def dfs(target, memo={}):
            # without memoization it wont pass 
            if target in memo:
                return memo[target]
            # base case changes depending on your logic
            if target == 0:
                return []
            if target < 0:
                return None
            shortest_combination = None
            for num in nums:
                remainder = target - num
                # this is where the decision tree is built
                result = dfs(remainder)
                # make sure not if result because result might be [] which yields to False
                if result != None:
                    # combination = result+[num]
                    combination = [*result, num]
                    # when we get the first result, we assign shortest_combination to that result.
                    # so shortest_combination == None this will be true only once
                    if shortest_combination == None or len(combination) < len(shortest_combination):
                        shortest_combination = combination
            memo[target] = shortest_combination
            return shortest_combination

        return -1 if dfs(target) == None else len(dfs(target))