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 I have been struggling with recursion. This problem can be solved with DP but before moving on to that concept I want to solve it using DFS to understand the problem first. I couldn't find a DFS example on the solutions. My first attempt fails some cases, e.g. [186,419,83,408], 6249. My thought process for the code below: The reverse is not needed; I just have it there to make it faster in the debugger. I am going to set up a backtracking template and loop through all the indexes trying every option. 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.) I keep calling backtracking trying to increment by the same coin until it doesn't work. If it fails I call another backtrack function incrementing the index to attempt to reach the final result. 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 <= amount: count += 1 backtrack(i,total + coins,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 Continue reading...
