We did almost this exact problem earlier this year on my course at uni but using the functional language ML, and actually returning a list of lists of ways to make the change. The solution is really neat in ML and since I have exams in a month or so I thought it wouldn't be such a bad idea for me to go over it and try to explain it to the other monks. I'll give the code first and then try and explain what it does.

1.    fun change (till, 0) = [[]]
2.      |  change ([], amt) = []
3.      |  change (coin::till, amt) = 
4.        if amt < coin then change(till, amt)
5.        else
6.        let fun allchange [] = []
7.            | allchange (cs::css) = (coin::cs) :: allchange css
8.        in allchange (change (coin::till, amt - coin)) @ change (til
+l, amt)
 9.       end;
[download]

The first line starts our function declaration and matches the input pattern of some list of coins that we can use (till) and an amount left over to make of 0. There is exactly one way to do this, an empty list of coins, so we return a list (the outer set of square brackets) containing the empty list (the inner set of square brackets). Line 2 is a second base case: we have run out of suitable types of coin, but we still need to make change. In this case there are no solutions so we return the empty list. From here onwards we get into the recursive magic, the case where we have a list of coins (the first of which is called coin, the rest of the list being contained in till) and an amount we are aiming to make. If the coin at the front of the list is too big, we simply discard it and try making change for that amount using the other coins in the till with a recursive call to change(till, amount) (line 4). Otherwise we define a new function allchange which takes a list of lists (cs is a list of coins, css is a list of such lists) and adds a coin to the front of all lists of coins in that list (line 7). We then call allchange on all the solutions found by the recursive call to change(till, amt-coin) and append (@) it to the list of ways of simply making change from coin (ie always taking the biggest coin we can).

Hopefully that makes sense, all the magic happens in line 8. It seemed like a pretty neat solution and short even in comparison with the Perl ones on offer (even if you do have to invest more brain power to understand it).