6 minute read

Subset sum, aka the coin change problem, is a very specific problem that for some reason gets mentioned a lot. The problem is very simple: given some coins of different values, what values of items can we buy with a subset of the given coins? Sometimes the problem statement asks, can we buy an item of a certain price with our coins without change? If not, what is the minimum amount of change needed? What if we have a number of the same coins, or even an infinite number? Many of these variants can be solved with some tweaks to the same code. So let’s start with the most basic formulation: given a vector of positive integers, return a vector of all integers that are subset sums (i.e. there exists a subset in the input vector with a sum equal to that number). There are many good ways to accomplish this task.

First attempt: iterative, boolean array

Let’s jump into the code directly:

vector<int> solution1(vector<int>& coins) {
    int total = 0;
    for (int x : coins)
        total += x;
    vector<bool> pos(total+1);
    pos[0] = true;
    for (int x : coins)
        for (int i = total; i >= 0; i--)
            if (pos[i])
                pos[i+x] = true;
    vector<int> ans;
    for (int i = 0; i <= total; i++)
        if (pos[i])
            ans.push_back(i);
    return ans;
}

OK, so first we calculated the total values of the coins, then we know all possible subset sums are in the range [0, total]. Then we constructed a boolean vector with indices in the same range, to indicate what values we can form. The algorithm proceeds by adding a new coin every iteration. Say we used to be able to pay {0, 1, 2, 3, 4, 5, 6}, and we have a new coin of value 10. Then by adding the new coin in, we can pay {10, 11, 12, 13, 14, 15, 16}. But we can also not use the new coin and pay [0, 6], so we need to keep that in the original array. Then we combine the two.

The most important part here is the loop for (int i = total; i >= 0; i–). It counts down, because counting up will lead to a logic error. Think of it this way: you could already pay 0, and you add a new coin of value 2 in, so you set pos[2] = true. And then you count up and see pos[2] is true - you will then set pos[4] to be true, although you already used the new coin in that combination! Counting down avoids this problem because every new element you set to be true will not be visited again in this iteration.

Second attempt: iterative, set of integers

vector<int> solution2(vector<int>& coins) {
    set<int> pos;
    pos.insert(0);
    for (int x : coins)
        for (auto it = pos.rbegin(); it != pos.rend(); it++)
            pos.insert(x+*it);
    return vector<int>(pos.begin(), pos.end());
}

The basic idea is the same, but instead of indicating val as possible by setting pos[val] = true, we insert it to the set. The code is much more concise.

Third attempt: recursive, set of integers

void soln3helper(vector<int>& coins, int idx, int val, set<int>& pos) {
    if (idx == coins.size()) {
        pos.insert(val);
        return;
    }
    soln3helper(coins, idx+1, val, pos);
    soln3helper(coins, idx+1, val+coins[idx], pos);
}

vector<int> solution3(vector<int>& coins) {
    set<int> pos;
    soln3helper(coins, 0, 0, pos);
    return vector<int>(pos.begin(), pos.end());
}

This is basically DFS, if you treat whether using a coin or not as an edge and a combination of coins as a vertex in the graph, you will get a tree. At the leaf nodes of the tree, insert the sum of the combination into the set.

Why the three approaches?

Each approach has its pros and cons. The second one has the least amount of code, and is easy to understand. The first one might be marginally more efficient for small test cases, because it only uses vectors but not any sets. Note however that the boolean vector could be huge if the coins are of really big values, in which case it would be very inefficient. The third one is intriguing because there is not any branch cutting. It incidentally takes care of negative coin values, which the other solutions do not. That means our runtime will always be the worst case runtime, 2^n where n is the number of coins. But is it really that bad? Let’s compare the runtimes:

First attempt: O(n*sum)

This is obvious from the nested loops. How big is sum though? The lower bound is n, when all the numbers are 1. In that case we get O(n^2) overall runtime. There is however not an upper bound - any coin can be arbitrarily big, and in that case we are kind of screwed.

Second attempt: O(n*2^n)

In the ith loop, we have at most 2^(i+1) items in the set. Looping through them and all insertions cost O(2^(i+1)*log(2^(i+1))) = O(i*2^i). Summing from i = 0 to i = n-1, we can see that each later term is larger than the previous term by 2 times at least, so we can drop all the front terms and only take the last, and we get the answer.

Third attempt: O(2^n)

Very simple: on each level i, we have 2^i edges coming out, i.e. O(2^i) work. Summing them gives O(2^n) by the same argument. From the runtime analyses, you can see either the first or the third algorithms could be optimal for different inputs. The second, however, is never asymptotically optimal. Even in the case of all 1s, it runs in O(n^2*log(n)). Hence it is most useful when you don’t really need that much performance but prefer pretty code instead (say, during an interview).

Fourth attempt: iterative, integer array

vector<int> solution4(vector<int>& coins) {
    vector<int> pos{0};
    for (int x : coins) {
        vector<int> newpos, next;
        for (int p : pos)
            newpos.push_back(p+x);
        int l = 0, r = 0;
        while (l < pos.size() r < newpos.size()) {
            if (l == pos.size() (r != newpos.size() && pos[l] >= newpos[r])) {
                if (next.empty() next.back() != newpos[r])
                    next.push_back(newpos[r]);
                r++;
            } else {
                if (next.empty() next.back() != pos[l])
                    next.push_back(pos[l]);
                l++;
            }
        }
        pos.swap(next);
    }
    return pos;
}

This is clearly a more elaborate approach to the problem. What we’re trying to achieve here is an O(2^n) algorithm that has a best case scenario of O(n^2), in the case of all 1s as input array. This is built mostly upon the second attempt, and we’re trying to eliminate the use of a set, since it inevitably gives us an extra time complexity factor. The way to accomplish this is to store the new values in a new vector, and merge the two vectors like in merge sort but removing all duplicates. In the ith iteration, we must only have O(2^i) amount of work, and summing through all i’s gives O(2^n).

Multiple coins

That’s about it, but one last discussion about multiple coins or infinite coins. Say we have the coins {3, 4, 7, 19} and we want to pay for an item of price 25, can we do it? Yes, 3+3+19 = 25. How do we do this? There are a few approaches, but here is one of them. I will build it on attempt 2:

bool multipleCoins(vector<int>& coins, int val) {
    set<int> pos;
    pos.insert(0);
    for (int x : coins)
        for (auto it = pos.rbegin(); it != pos.rend(); it++)
            for (int v = x+*it; v <= val; v += x)
                pos.insert(v);
    return pos.count(val);
}

Instead of pushing in only one value, we keep pushing in more values with more coins of the same type until we go over the desired value. Of course we can immediately return true if we find val, which could potentially save a lot of work. But this is good enough as an example to show how to modify the above versions to account for multiple coins.

Categories:

Updated: