递归 - Python硬币组合列表

-4

我目前正在尝试编写一些代码，给定一个硬币值列表，将返回所有可能的硬币总和合计值。这里有一个程序应该如何运行的例子：递归 - Python硬币组合列表

>>> find_changes(4,[1,2,3]) 
[[1, 1, 1, 1], [2, 1, 1], [1, 2, 1], [3, 1], [1, 1, 2], [2, 2], [1, 3]]

我得到了下面的代码模板填写：

def find_changes(n, coins): 
    if n < 0: 
     return [] 
    if n == 0: 
     return [[]] 
    all_changes = [] 

    for last_used_coin in coins: 
     ### DELETE THE "pass" LINE AND WRITE YOUR CODE HERE 
     pass 

    return all_changes

我使用for循环内的以下代码尝试：

all_changes.append[last_used_coin] 
find_changes(n-last_used_coin,coins)

目前无法使用。我究竟做错了什么？

来源

2013-11-14 user2928714

什么是它应该做的？出了什么问题？家庭作业需要更多的努力... – sdasdadas

是的，我知道，它应该返回给我们所有可能的组合列表的列表，我是新的Python递归，所以..... – user2928714

你应该先数字了解你的基本情况，然后弄清楚如何将问题分解成更小的子问题。如果这很难（因为这不是最简单的递归问题），首先尝试解决像斐波那契递归这样的问题。 – sdasdadas

您的回答很接近，但由于语法错误和逻辑错误的组合而失败。

记住，append是一个方法调用 - 你想添加一组括号周围的支架，像这样：

all_changes.append([last_used_coin]) 
# Add a list of one element to the `all_changes` list

但是，你的代码还没有做相当的工作。让我们试着挑选代码。

如果我们看看您的for循环，它会遍历列表中的每一枚硬币。您采取了正确的下一步 - 您通过您的线路find_changes(n - last_used_coin, coins)找到了所有可能的硬币组合n - last_used_coin。

现在，您需要做的就是遍历所有可能的硬币组合，从调用find_changes开始，在last_used_coin上重新添加，并将所有内容附加到all_changes列表中。

这里的决赛中，工作代码：

def find_changes(n, coins): 
    if n < 0: 
     return [] 
    if n == 0: 
     return [[]] 
    all_changes = [] 

    for last_used_coin in coins: 
     combos = find_changes(n - last_used_coin, coins) 
     for combo in combos: 
      combo.append(last_used_coin) 
      all_changes.append(combo) 

    return all_changes 

print find_changes(4, [1,2,3])

来源

2013-11-14 18:05:50 Michael0x2a

非常感谢Michael，我非常感谢！ – user2928714

尽管我完全理解如何将其应用于数学递归定义，但它需要时间来适应递归思维。 – user2928714

存在一个问题，输出为：[[[[[[1]，1]，1]，[[2] ，[1]，[1]，1]，[[[1]，1]，[[1]，1]，[[2]，1] 1]，[1]，[1]，[1]，[[1]，[[1]，[[2] ，[1]，1]，[[[1]，2]，1]，[[3]，1]]，[[[[1]，1]，[1]，[[2]，1 ] [1,1,1]，[[[1]，1]，1]，[[2]，1]，1,1]，[[[1]，2]，1]，[[3]， 1]，[[1]]，[[[1]，1]，[[2]，1]，[1] ] [1]，[1]，[2]，1]，[[3]，1]]，[[[1]，2] [[[1]，1]，2]，[[2]，2]]，[[[1]，3]]] – user2928714

递归 - Python硬币组合列表

回答

相关问题