Enumerating all n-integer Sets Which Sum to an Integer x

I came up with what I think is an elegant use of monadic code, while working on a program to compute solutions to the Postage Stamp Problem. The problem asks:

Consider that an envelope is able to hold a limited number of postage stamps. Then, consider the set of the values of the stamps – positive integers only. Then, what is the smallest total postage which cannot be put onto the envelope?

The algorithm below takes a number of stamps that can fit and a total postage to apply and returns a list of all the sets of different stamp values that can be combined to form the target postage sum:

sumLists :: Int -> Int -> [[Int]]
sumLists = f 0 where
    f _ 1 n = return [n]
    f i c n = do a <- [i.. div n c]
                 as <- f (i+a) (c-1) (n-a)
                 return (a : as)

Thus the potential stamp combinations for a letter which can hold three stamps and costing 5 cents to mail would be:

*Main> sumLists 3 5 [[0,0,5],[0,1,4],[0,2,3],[1,1,3],[1,2,2]]

As you can see, the algorithm also produces ordered lists naturally!

But perhaps all we care about are unique stamp values that. If we want to adjust our goal such that the algorithm returns a list of all sets of unique stamp values sufficient to create the target postage, we need only adjust the return line:

return (a : dropWhile (==a) as)

Similarly we could drop the zeros (which mean “no stamp” in our case) from the beginnings of each set if we desired. The above code have applications to many similar problems including Subset Sum, and Knapsack as well as other partitioning problems.