Actually, something along the lines of Dinh's attempted solution to the original partition problem is a very nice solution to the coin changing problem: Make change for the amount a, using at most k of the coins cs.

coins _ 0 _ = [[]] coins _ _ 0 = [] coins cs a k = [h:s | t <- init (tails cs), let h = head t, h <= a, s <- coins t (a-h) (k-1)]

(The functions "init" and "tails" are from the Data.List module.) Note that Dinh is already using a monad for his solution, via Haskell's special syntax for the List monad. Here it is translated into regular monad syntax:

coinsM _ 0 k = return [] coinsM _ _ 0 = [] coinsM cs a k = do t <- init (tails cs) let h = head t unless (h <= a) [] s <- coinsM t (a-h) (k-1) return (h:s)

(The function "unless" is from the Control.Monad module.) -Yitz