I recently tried coming up with an algorithm that uses dynamic programming for the counting variant of the change problem. Given a set of target and a set of denominations, print the number of possible combinations that add up to the target. So if my target is 5 and my set is { 1, 2, 5, 10 } then the solution is 4. More information can be found on: http://www.wcipeg.com/wiki/Change_problem

Although the solution to this particular problem is a single number, I instead decided to list all possible combinations. My reasoning was that if I list all combinations then it'll be easier for me to work out whether or not my algorithm is working. I assumed that these two problems are identical other than the obvious difference that the form of the output is different. But I really struggled with coming up with a dynamic programming solution for listing all combinations (recursive algorithm wasn't an issue). Since then I've been trying to find such an algorithm online but I'm surprised that it doesn't seem to exist. So I'm wondering if my assumption is incorrect and these are actually two separate problems.

I'm aware that when solving problems like this I should focus on just what's required to make things a little easier, but I didn't think it'd result in two completely separate problems. So there are actually THREE variants of change problem:

• optimisation problem where I work out the smallest number of coins required to meet my target (the same algorithm can be used for both working out the minimum number of coins required AND also the actual minimum set of coins)
• counting problem which lists number of possible combinations (can be solved using dynamic programming AND recursion)
• listing set of possible combinations (can only be solved using recursion)

Is this correct? Are these separate problems?