-3

I'm currently trying to write some code which, given a list of coin values, will return all the possible combination of coins summing up to some value. Here's an example of how the program should run:

>>> 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]]

I was given the following code template to fill out:

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

I tried using the following code inside the for loop:

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

It's currently not working. What am I doing wrong?

4

1 回答 1

6

Your answer was close, but was failing due to a combination of syntax errors, and logic errors.

Remember, append is a method call -- you want add a set of parenthesis around your brackets, like so:

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

However, your code still doesn't quite work. Let's try picking through the code.

If we look at your for loop, it's looping through every possible coin in your list. You took the correct next step -- you found all the possible coin combinations for n - last_used_coin through your line find_changes(n - last_used_coin, coins).

Now, all you need to do is iterate through all the possible coin combos from calling find_changes, add back on last_used_coin, and append everything to the all_changes list.

Here's the final, working code:

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-14T18:05:50.563 回答