Typical coin change program in python that asks for specific amounts of each coin
<p>Given a number "x" and a sorted array of coins "coinset", write a function that returns the amounts for each coin in the coinset that sums up to X or indicate an error if there is no way to make change for that x with the given coinset. For example, with x=7 and a coinset of [1,5,10,25]a valid answer would be {1: 7} or {1: 2, 5: 1}. With x = 3 and a coinset of [2,4] it should indicate an error.</p>

<p>I know of this code for coin change</p>

<pre><code>def change(n, coins_available, coins_so_far):
    # n is target
    result = []
    if sum(coins_so_far) == n:
        yield coins_so_far
    elif sum(coins_so_far) &gt; n:
        pass
    elif coins_available == []:
        pass
    else:
        # multiple occurences of the same coin
        for c in change(n, coins_available[:], coins_so_far+[coins_available[0]]):
            yield c
        for c in change(n, coins_available[1:], coins_so_far):
            yield c

n = 5
coins = [1,5,10,25]

solutions = [s for s in change(n, coins, [])]
for s in solutions:
    print(s)
</code></pre>

<p>But what if you can only use two parameters (n and coins_available). How could one possibly condense this. This is the only coin change code I've seen that actually shows the amounts for each coin. </p>

<p>As a concept, change <strong>coins_so_far</strong> to <strong>coins_this_call</strong>.</p>

<p>Your recursion steps change to something of this ilk; although it's not complete, I hope you see the idea.</p>

<pre><code>for c in change(n-sum(coins_this_call), coins_available[:]):
    yield coins_this_call.append(c)
</code></pre>

<p>You locally keep the count of coins at the current denomination -- don't pass the whole load through the recursions.  When you recur, instead of passing the original amount as well as the coins already used, simply pass the <em>remaining</em> problem.  When that returns with solutions, append the current level's solution, returning the augmented list to whatever called <em>this</em> instance.</p>

<p>Is that enough hint to get you moving?</p>

python algorithm python-2.7 data-structures