Are counting problems the same as problems involving listing all possible combinations? 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?



Edit:
I should mention that I did come up with this algorithm that uses dynamic programming but I think it only works for certain sets of denominations hence why I said that I failed to come up with an algorithm.

int main()
{
    std::unordered_map&lt;int, std::vector&lt;std::pair&lt;std::vector&lt;int&gt;, int&gt;&gt;&gt; m;
    m[1].push_back({ { 1 }, 1 });

    const int target = 25;
    const std::vector&lt;int&gt; coins = { 200, 100, 50, 20, 10, 5, 2, 1 };

    for (int i = 2; i &lt;= target; i++) // N
    {
        std::unordered_set&lt;int&gt; s;

        for (auto coin : coins) // M
        {
            if (coin &gt; i) continue;
            if (coin == 1)
            {
                m[i].push_back({ { i }, 1 });
                s.insert(1); // constant
            }

            for (auto v : m[i - coin]) // N
            {
                if (s.find(v.second + 1) != s.end()) continue; // constant
                std::vector&lt;int&gt; temp_v = v.first;
                temp_v.push_back(coin); // constant
                m[i].push_back({ temp_v, v.second + 1 }); // constant
                s.insert(v.second + 1); // constant
                std::cout &lt;&lt; i &lt;&lt; ": ";
                PRINT_ELEMENTS(temp_v);
            }
        }
    }

    return 0;
}


The trick I'm using is that for a given target, each combination has a unique number of elements. E.g. for target 5 the combinations are {5}, {2, 2, 1}, {2, 1, 1, 1}, and {1, 1, 1, 1, 1} and as you can see the cardinality of each set is unique. This won't work if, let's say, the denominations were {1, 2, 3, 5, 6} and the target was 8. In that case I can store use arrays/vectors to represent combinations and store them in a set but I'd have to sort each vector first (so that they can be easily compared) and that increases the complexity of my solution quite a bit I think.
First of all note it is an NP complete problem if you are searching for a specific subset of denominations that sums to a particular integer.

You could solve this problem by brute-force simply generating all subsets of coins checking each time that the set adds up to the target. Time complexity of this algorithm is terrible, though there are pseudo-polynomial solutions too.

A counting problem which lists the number possible outputs doesn't have to be solved using recursive algorithm though a recursive algorithm in particular for generating subsets is much more shorter, intuitive, and readable.

Any recursive algorithm may be rewritten in a nonrecursive form. Similarly, there is nothing special with dynamic programming, it is just a way to solve a problem. But not all counting problems (or any problem) are solved or have to be solved using DP.

Also, once you generated a list of sequences or sets then of course you could count, in other words your listing solves corresponding counting problem. However, if you are interested just in the number of elements/sequences/sets then you don't have to list/generate sets. For example given $n$ you could compute that the total number of binary strings of length is $2^n$ without generating these strings. Computing $2^n$ is easier than listing all strings. Similarly, if you are interested in the number of subsets of size $m$ of a set of size $n$, then that value is $\binom{n}{m}$ which may be calculated using the Stirling's approximation. But listing all possible subsets is harder. 

Thus counting problems ARE NOT always same as problems involving listing all possible combinations.