固定硬币变化回溯解决方案（暴力破解）

Question

我知道这个解决方案的最佳问题是使用动态规划。但是，我想尝试这种蛮力回溯方法，我从数量中减去硬币并尝试找到与该数量匹配的组合，并在数量为 0 时找到组合数组长度的最小值。但是，此递归调用并未正确检查所有组合。请以尽可能少的更改来编辑我的代码，因为这将帮助我了解在提出回溯解决方案时我做错了什么。这是我的代码 -

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

Answer 1

我是 LeetCode 的 7yier，你向他寻求帮助。这是固定代码

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

看来问题出在您更改当前金额的地方。不要在新行上更改它，而是将其传递给已更改的回溯函数。我指的是 backtrack(cur - c, arr) 部分。

固定硬币变化回溯解决方案（暴力破解）

Fixing coin change Backtracking solution(bruteforce)

python

backtracking

recursive-backtracking