pythonbacktrackingrecursive-backtracking

Fixing coin change Backtracking solution(bruteforce)


I know the optimal problem for this solution is using dynamic programming. However, I wanted to try this bruteforce backtracking approach where I subtract the coin from the amount and try to find combinations that match that amount and find the minimum of the length of the combinations array once the amount is 0. However, this recursive call does not correctly check all combinations. Please edit my code with the least amount of changes possible because that will help me understand what I do wrong while coming up with a backtracking solution. Here is my code -

class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
    if amount == 0: 
        return 0  
    output = amount+1
    def backtrack(cur,arr):
        if cur == 0:
            print("happening")
            nonlocal output
            output = min(output,len(arr))
            return
        if cur<0:
            return
        
        for c in coins:
            print(cur,c,arr)
            if (cur-c) >=0:
                cur-=c
                arr.append(c)
                backtrack(cur,arr)
                arr.pop()
            else:
                continue

    arr = []
    backtrack(amount,arr)
    return output

Solution

  • class Solution:
        def coinChange(self, coins: List[int], amount: int) -> int:
            if amount == 0: 
                return 0  
            output = amount+1
            def backtrack(cur,arr):
                if cur == 0:
                    nonlocal output
                    output = min(output,len(arr))
                    return
                if cur<0:
                    return
    
                for c in coins:
                    if (cur-c) >=0:
                        arr.append(c)
                        backtrack(cur - c,arr)
                        arr.pop()
                    else:
                        continue
    
            arr = []
            backtrack(amount,arr)
            return output
    

    Looks like the issue is where you are altering the current amount. Instead of altering it on a new line, pass it into the backtrack function altered. I am referring to the backtrack(cur - c, arr) part.