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>You want something like:</p>

<pre><code>def change(amount, coins):
    '''
    &gt;&gt;&gt; change(10, [1, 5, 25])
    [5, 5]
    '''
    if not coins or amount &lt;= 0:
        return []
    else:
        return min((change(amount - coin, coins) + [coin]
                    for coin in coins if amount &gt;= coin), key=len)
</code></pre>

<p>As an aside, this is not a dynamic programming solution. This is a simple recursive algorithm which will not scale for very large inputs.</p>

python recursion dynamic-programming