Are counting problems the same as problems involving listing all possible combinations?

Question

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.

Answer 1

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.

Answer 2

Usually it is easy to adjust a dynamic programming algorithm that checks for the existence of a solution, so it outputs a solution (or all solutions).

When we only care about existence of a solution, the usual algorithm is to create an array $A[1..n]$, where $A[i]$ gets set to true if there exists a subset of coins that sums to $i$, or false if not, and $n$ is the target. We can calculate $A[i]$ in terms of $A[1..i-1]$, e.g., $A[i] = A[i-c_1] \lor A[i-c_2] \lor \cdots \lor A[i-c_k]$ where $c_1,\dots,c_k$ are the coin denominations. Let's adjust that to output all solutions. How? We'll add an auxiliary array $B[1..n]$, where $B[i]$ contains a list of all subsets that sum to $i$ (or the empty list if none exists). Notice that we can compute $B[i]$ as a function of $B[1..i-1]$, namely,

$$B[i] = B[i-c_1] \cup B[i-c_2] \cup \cdots \cup B[i-c_k].$$

Alternatively, we can think of this as a graph problem. Construct a graph with vertices $0,1,2,\dots,n$ -- one vertex for each possible sum (up to the target $n$). For each coin denomination $c_i$ and each sum $j$, add the edge $j \to j+c_i$ to the graph. Now the existence problem asks "does there exist a path from $0$ to $n$ in this graph?". If you want to list all solutions, the problem becomes "list all paths from $0$ to $n$ in this graph", so your problem reduces to listing all paths from one vertex to another in a dag. There are standard algorithms for that, which you can find via a web search.

Answer 3

The complexity of listing all the solutions is at least O (f (n)), where f (n) is the number of solutions. There are plenty of problems where f (n) can be computed in o (f (n)), which would be asymptotically faster than f (n).

As an extreme example, "count the number of permutations of the integers 1 to n" vs. "list all permutations of the integers 1 to n". The latter takes O (n!). Counting the number of solutions is nothing more than calculating n!, which can be easily done in $O (n^2 \log^2 n)$ (faster with a bit of effort).

There are even situations where you can prove the existence of exactly one solution, but the solution is hard to find. For example, if the problem is finding an RSA encrypted number, it is trivial to count the number of solutions (the number is 1), but very, very hard to find a solution.

On the other hand, there are problems where the only way to determine that a solution exists is to find it. In that case, counting and listing the solutions will take about the same time.