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
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.