Have to display coins used in makeChange function?
<p>I am creating a makeChange function using a useIt or loseIt recursive call. I was able to determine the least amount of coins that's needed to create the amount; however, I am unsure as to how to display the actual coins used.</p>

<pre><code>def change(amount,coins):
    '''takes the amount and makes it out of the given coins in the list in order to return the least number of coins that's needed to create the value and the coins used'''
    if amount==0:
        return 0
    if coins== [] or amount &lt; 0:
        return float('inf')
    else:
        useIt= change(amount,coins[1:])
        loseIt= change(amount-coins[0],coins) + 1

    return min(useIt,loseIt)
</code></pre>

<p>First of all the semantics of your names for the use-it-or-lose-it strategy are backwards. "Use it" means the element in question is being factored into your total result. "Lose it" means you're simply recursing on the rest of the list without considering the current element. So I'd start by switching those names around. And also you should be discarding the current element in the recursive call, whether or not you use it:</p>

<pre><code>loseIt = change(amount,coins[1:])
useIt = change(amount-coins[0], coins[1:]) + 1
</code></pre>

<p>Now that we've fixed that, on to your question about passing the result down. You can take the <code>min</code> of tuples or lists, and it will start by comparing the first elements of each, and continue on successive elements if no definite <code>min</code> is yet found. For example if you pass around a list with an integer and a list:</p>

<pre><code>&gt;&gt;&gt; min([2, [1,2]], [3, [0,2]])
[2, [1, 2]]
</code></pre>

<p>You can also combine any number of elements in this form with an expression like this:</p>

<pre><code>&gt;&gt;&gt; [x+y for x,y in zip([2, [1,2]], [3, [0,2]])]
[5, [1, 2, 0, 2]]
</code></pre>

<p>but your case is easier since you always are just combining 2 of these, so it can be written more like: </p>

<pre><code>[useIt[0] + 1, useIt[1] + [coins[0]]]
</code></pre>

<p>Note that the first element is an integer and the second a list.</p>

<p>in your case the implementation of this idea would look something like:</p>

<pre><code>def change(amount,coins):
    if amount==0:
        return [0, []]
    if coins== [] or amount &lt; 0:
        return [float('inf'), []]
    else:
        loseIt = change(amount, coins[1:])
        useIt = change(amount - coins[0], coins[1:])
    # Here we add the current stuff indicating that we "use" it
    useIt = [useIt[0] + 1, useIt[1] + [coins[0]]]
    return min(useIt,loseIt)
</code></pre>

python recursion dynamic-programming