用递归在Python中更改硬币/为什么不工作

Question

这是我的代码。换硬币的任务。我需要一份清单，包括交换选项。

a = []
def coinChange(coins, amount, result=None):
if result is None: 
result = []

if amount < 1 and sum(result) == 3:
return a.append(result)
else:
for i in coins:
if amount - i >= 0:
result.append(i)
coinChange(coins, amount - i, result)            
return 
coinChange([1,2,3], 3)
print(a)

他们返回

[1,1,1,2,2,1,3]

但我需要一份清单。每个子列表应该只包含那些加起来为3的数字。

例如：

[[1,1,1], [2,1], [3]]

我如何获得这样的列表？感谢

Answer 1

我甚至会进一步接受DarrylG的答案，并建议不要通过递归堆栈传递结果，因为这会使递归的整个概念变得复杂。

简单地说，你通常应该：

1. 假设您可以解决较小版本的问题(这正是您正在实现的函数(
2. 使用较小问题的解决方案来解决原始问题(递归步骤，在这里您调用函数(
3. 为问题的最简单情况定义一个显式解决方案，这本质上是递归的停止条件

以下是使用以下提示解决问题的示例代码：

def coinChange(coins, sum):
# Stop condition.
if sum == 0:
return [[]]
# Recursive step
solutions = []
for i, coin in enumerate(coins):
if coin <= sum:
lst = coinChange(coins[i:], sum - coin)
solutions.extend([[coin] + l for l in lst])
return solutions

print(coinChange([1, 2, 3], 3))

运行结果：

[[1, 1, 1], [1, 2], [3]]

检查你是否在没有依赖性的情况下完成了这些步骤的一个好测试是尝试用一行代码：

def coinChange(coins, sum):
return [[c] + l for i, c in enumerate(coins) if c <= sum for l in coinChange(coins[i:], sum - c)] if sum > 0 else [[]]

请注意，有时它可能不可读，所以你决定把它保持在一行的形式。

Answer 2

简单解决方案

代码

def coinChange(coins, amount, result=None, solutions = None):
'''
result - stores current set of coins being tries
soltions - solutions found so far
'''
if result is None: 
result = []

if solutions is None:
solutions = []
if amount == 0:
# Add solution
solutions.append(result[:])  # append a copy since result will change
elif amount > 0:
for i in coins:
if amount - i >= 0:
# Adding i to list of coins to try
coinChange(coins, amount - i, result + [i,], solutions)

return solutions

测试

a = coinChange([1,2,3], 3)
print(a)

# Capture the solution in a (i.e. don't make it global--generally bad practice)         
a = coinChange([1,2,3], 3)
print(a)

输出

[[1, 1, 1], [1, 2], [2, 1], [3]]

使用生成器更简单

def coinChange(coins, amount, result=None):
'''
result - stores current set of coins being tries
soltions - solutions found so far
'''
if result is None: 
result = []

if amount == 0:
# report solution
yield result

if amount > 0:
for i in coins:
yield from coinChange(coins, amount - i, result + [i,])    

a = list(coinChange([1,2,3], 3))
print(a)

使用缓存

通过修改GalSuchetzky的答案，最容易说明缓存的使用。

问题

• 由于参数不可哈希，因此无法直接在coinChange函数上使用缓存(例如，coins是一个列表，因此不可哈希(
• 我们通过使用一个嵌套函数(helper(来实现这一点，该函数的参数是可哈希的，并根据需要索引到硬币中

代码

def coinChange(coins, sum_):
'''
Inputs:
coins - list of coins
sum_  - value coin should sum to (use sum_ since sum is a builtin function)
'''

def coinChangeHelper(j, total):
'''
Uses cache to compute solutions

Need helper function since coins is a list so can't be hashed to placed in cache

Inputs:
j     - current index into coins
total - current sum
'''
if (j, total) in mem_cache:
# Use cache value
return mem_cache[(j, total)]

# Stop condition.
if total == 0:
mem_cache[(j, total)] = [[]]
else:
# Recursive step
solutions = []
for i in range(j, len(coins)):
if coins[i] <= total:
lst = coinChangeHelper(i, total - coins[i])
solutions.extend([[coins[i]] + l for l in lst])
mem_cache[(j, total)] = solutions

return mem_cache[(j, total)]
# Init cache
mem_cache = {}

return coinChangeHelper(0, sum_)
print(coinChange([1, 2, 3], 3))