递归换币问题给出错误答案

Question

为什么我的代码，打印出" Found solution ";4次中的7次当硬币是[1,2,3]时美分的变化是4。应该只有4种可能的解决方案。我在这里做错了什么?

def coinChange(nCents, coins, total):
if (total == nCents):
print("Found solution")
return 
if (total > nCents):
return
if (total < nCents):
for i in range(len(coins)):
coinChange(nCents, coins, total+coins[i])
coins = [1,2,3]
coinChange(4, coins, 0)

Answer 1

直接回答为什么可以通过跟踪您使用的硬币并将结果打印出来来找到。这将清楚地说明为什么你得到七个结果:

def coinChange(nCents, coins, total, coin_list = None):
if coin_list is None:
coin_list = []
if (total == nCents):
print("Found solution", coin_list)
return 
if (total > nCents):
return
if (total < nCents):
for i in range(len(coins)):
coinChange(nCents, coins, total+coins[i], coin_list + [coins[i]])
coins = [1,2,3]
coinChange(4, coins, 0)

这个打印:

Found solution [1, 1, 1, 1]
Found solution [1, 1, 2]
Found solution [1, 2, 1]
Found solution [1, 3]
Found solution [2, 1, 1]
Found solution [2, 2]
Found solution [3, 1]

可以看到，得到这个结果是因为它认为[1, 1, 2]、[1, 2, 1]和[2, 1, 1]这样的解是不同的。

Answer 2

这不是对PO的直接回答。但它更倾向于展示另一种方法——动态规划方法来解决同样的问题:

def coin_ways(coins, amount):
dp = [[] for _ in range(amount+1)]

dp[0].append([])      # or table[0] = [[]], if prefer
for coin in coins:
for x in range(coin, amount+1):
dp[x].extend(ans + [coin] for ans in dp[x-coin])
#print(dp)

return dp[amount]

if __name__ == '__main__':
coins = [1, 2, 3]  # 

print(coin_ways(coins, 4))