CODEWITHSUNDEEP
pythonbacktrackingrecursive-backtracking
Web Developer
Web Developer

Reputation: 13

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

Upvotes: 0

Views: 230

Answers (1)

John
John

Reputation: 26

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.

Upvotes: 1

Related Questions