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<int, std::vector<std::pair<std::vector<int>, int>>> m;
    m[1].push_back({ { 1 }, 1 });

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

    for (int i = 2; i <= target; i++) // N
    {
        std::unordered_set<int> s;

        for (auto coin : coins) // M
        {
            if (coin > 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<int> 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 << i << ": ";
                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.