我开始编写和理解硬币变化问题，无法获得直觉，所以我开始编写一个蛮力解决方案。我想在进入记忆之前了解蛮力解决方案。
coins = [2, 3, 7]
change = 12
def coin_change(c):
print(c)
if c <= 0:
return 0
else:
for i in coins:
if c - i >= 0:
coin_change(c - i)
coin_change(change)
它打印出剩下的几个更改，但我不知道如何将每个路径存储在数组中。
我还想了解如何使用递归来跟踪路径。我可以考虑在coin_change中添加一个额外的参数，但也许还有另一种方法。
我对它的复杂性感到困惑。它的每一步都有许多硬币调用，但许多在线资源都提到它是 2n。
编辑：请注意，硬币供应是无限的，答案是4
[2, 2, 2, 2, 2, 2]
[3, 3, 3, 3]
[2, 2, 2, 3, 3]
[2, 3, 7]
了解硬币变化问题：
假设您指的是用最少数量的硬币计算零钱的问题，这里的关键思想是将问题视为在每一步做出选择——在这种情况下是"接下来要分配什么硬币？
您可以将问题分解为coin_change(score) = 1 + min{coin_change(score - c1), coin_change(score - c2), ...}您拥有的硬币c1, c2...在哪里。
跟踪路径：
这是相当简单的。无需返回解决方案(最小硬币组合(，只需返回所有可能性(所有硬币组合(。因此，当你对 (score-c1( 进行递归调用时，你会得到制造 (score-c1( 的所有硬币组合，您只需将 c1 添加到它们中即可。
代码
coins = [2, 3, 7]
change = 12
def coin_change(c):
if c == 0:
return [[]] # the only combo possible is no coins
if c < 0:
return [] # no combos possible
else:
all_combos = []
for i in coins:
recursive_result = coin_change(c-i)
for combo in recursive_result:
combo.append(i)
all_combos.extend(recursive_result)
return all_combos
result = coin_change(change)
for combo in result:
print(combo)
注意：这将为您提供所有排列。如果顺序无关紧要，您可以使用集合来删除重复项
编辑：在评论之后，这是删除重复项的代码
coins = [2, 3, 7]
change = 12
def removeDuplicates(combos):
filtered = set()
for combo in combos:
combo.sort()
filtered.add(tuple(combo))
return [list(i) for i in filtered]
def coin_change(c):
if c == 0:
return [[]] # the only combo possible is no coins
if c < 0:
return [] # no combos possible
else:
all_combos = []
for i in coins:
recursive_result = coin_change(c-i)
for combo in recursive_result:
combo.append(i)
all_combos.extend(recursive_result)
return removeDuplicates(all_combos)
result = coin_change(change)
for combo in result:
print(combo)
下面是一个获取硬币所有路径的示例。通常，当您编写递归函数时，您希望 1( 具有退出递归的条件，以及 2( 编写如何扩展前面的递归步骤。
coins = [2, 3, 7]
change = 12
def coin_change_paths(paths):
if all(sum(path)>=change for path in paths):
return paths
new_paths = []
for path in paths:
if sum(path)<change:
new_paths.extend(path+[c] for c in coins)
else:
new_paths.append(path)
return coin_change_paths(new_paths)
paths = coin_change_paths([[2],[3],[7]])
这不考虑重复。为此，您应该排序然后重复数据删除：
paths = [sorted(p) for p in paths]
temp = []
for p in paths:
if p not in temp:
temp.append(p)
paths = temp
您仍然必须检查哪些是有效的。
paths = [p for p in paths if sum(p)==change]
print(paths)
尝试看看是否可以将它们组合在一起并简化代码。
另一种可能的方法是使用带有yield和yield from的递归生成器函数。这样就无需将发现的组合保存在列表中，然后必须返回该列表：
coins = [2, 3, 7]
change = 12
def coin_change(c = []):
if sum(c) == change:
yield tuple(sorted(c))
else:
for i in coins:
if sum(c+[i]) <= change:
yield from coin_change(c+[i])
print(list(map(list, set(coin_change()))))
输出：
[[3, 3, 3, 3], [2, 2, 2, 3, 3], [2, 3, 7], [2, 2, 2, 2, 2, 2]]