Target sum by transforming to subset sum

Why this matters

Take the numbers 1, 1, 1, 1, 1 and a target of 3. Put a plus or minus sign in front of each number, add them up, and count how many sign choices give 3. One answer is +1 +1 +1 +1 -1. The question asks for the number of answers, not one answer.

With five numbers there are 2 to the power of 5, which is 32, sign patterns to try. With 40 numbers there are more than a trillion. A program that tries every pattern is too slow for that size. This lesson shows how to turn the sign question into a subset question, which dynamic programming (DP, a method that builds an answer from answers to smaller parts) can count quickly.

The previous lesson on partition asked yes or no: can a group reach a target? This lesson asks how many groups reach it. The table is the same kind of table, but each cell stores a count instead of a true or false.

The idea: signs become two groups

Give each number either a plus sign or a minus sign. The numbers with a plus sign form a group called P. The numbers with a minus sign form a group called N. Let T be the total of all the numbers.

Two facts follow from that setup.

The plus group and the minus group together make all the numbers, so P + N = T.

The result of the signs is the plus group minus the minus group, so P - N must equal the target.

Now solve those two equations for P. Add them: 2P = T + target, so P = (T + target) / 2. The problem is now: count the subsets of the numbers that add up to P. Each such subset becomes the plus group, and the rest become the minus group. Each subset gives exactly one sign pattern, and each sign pattern gives exactly one subset, so the two counts are equal.

Check this with 1, 1, 1, 1, 1 and target 3. The total is T = 5, so P = (5 + 3) / 2 = 4. A subset of these numbers that adds to 4 must leave out exactly one of the five 1s. There are five ways to choose which one to leave out. So the answer is 5, and it is the same as the count of sign patterns.

You can check one of these by hand. Leave out the third 1. The plus group is the four other 1s, which add to 4. The minus group is the single 1 you left out. The result is +1 +1 -1 +1 +1, which equals 3.

Worked example 1: a small list

Take 1, 2, 3 and a target of 2. The total is T = 6, so P = (6 + 2) / 2 = 4. We need the subsets of 1, 2, 3 that add to 4. Only one works: {1, 3}. The plus group is 1, 3 and the minus group is 2. The result is 1 + 3 - 2 = 2, which is the target. The answer is 1.

Here is a table that counts subsets, built one number at a time. The cell ways[s] is the number of subsets of the numbers used so far that add to s. Start with ways[0] = 1, because the empty subset adds to 0, and every other entry as 0.

The last row says ways[4] = 1, which matches the answer found by hand.

Each number x adds to the table in one rule: the new count for s is the old count for s plus the old count for s - x. The old count for s covers subsets that leave x out. The old count for s - x covers subsets that take x in. Both kinds of subset are counted, and no subset is counted twice.

The rule has to read the old values. If x is 1 and you walk upwards, ways[2] would read the new ways[1], which already counts a subset that used the 1. That counts the same 1 twice. So the loop walks downwards from P to x, as the code below does.

The parity test

Parity means whether a whole number is odd or even. The value P = (T + target) / 2 only makes sense when T + target is even. If it is odd, no subset can give exactly half of it, so the answer is 0 without any counting.

Why does parity decide this? Each sign flip changes the total by twice a number. Changing a plus sign to a minus sign on a number x moves the total from +x to -x, a change of 2x. A change of 2x never changes whether a total is odd or even. So every sign pattern has the same parity, and that parity is the parity of T. A target with the other parity is impossible.

Take 1, 2, 3, 4 and target 1. The total is 10 and the target is 1. Their sum is 11, which is odd, so the test returns 0. Check it by hand: every sign pattern gives an even total, because 10 - 2 * (sum of the minus numbers) is always even. A target of 1 can never appear.

The range test is simpler. If the absolute value of the target is larger than T, no signs can reach it, because the largest possible result is T, with every sign plus. Then the answer is 0 straight away. For 1, 2 and target 4, the total is 3, and 4 is larger than 3, so the answer is 0.

The code

The code below does the range test, the parity test, and then the subset count.

#include <iostream>
#include <numeric>
#include <vector>
 
// Count the ways to give each number a plus or minus sign so the result is target.
long long countTargetSum(const std::vector<int>& nums, int target) {
    long long total = std::accumulate(nums.begin(), nums.end(), 0LL);
    long long absTarget = target < 0 ? -static_cast<long long>(target) : target;
    if (absTarget > total) return 0;         // no signs can reach a value this far away
    long long want = total + target;         // equals 2 * P, where P is the plus group sum
    if (want % 2 != 0) return 0;             // parity test: P would not be a whole number
    long long P = want / 2;
 
    std::vector<long long> ways(P + 1, 0);   // ways[s] = number of subsets that add to s
    ways[0] = 1;                             // the empty subset adds to 0
    for (int x : nums) {
        for (long long s = P; s >= x; --s) { // downwards, so each number is used once
            ways[s] += ways[s - x];
        }
    }
    return ways[P];
}
 
int main() {
    std::cout << "[1, 1, 1, 1, 1], target 3: " << countTargetSum({1, 1, 1, 1, 1}, 3) << "\n";
    std::cout << "[1, 2, 3], target 2: " << countTargetSum({1, 2, 3}, 2) << "\n";
    std::cout << "[1, 2], target 4: " << countTargetSum({1, 2}, 4) << "\n";
    std::cout << "[1, 2, 3, 4], target 1: " << countTargetSum({1, 2, 3, 4}, 1) << "\n";
    std::cout << "[0, 0, 1], target 1: " << countTargetSum({0, 0, 1}, 1) << "\n";
}

Compile it with a C++20 compiler and warnings on:

g++ -std=c++20 -Wall -o target target.cpp
./target

The output is:

[1, 1, 1, 1, 1], target 3: 5
[1, 2, 3], target 2: 1
[1, 2], target 4: 0
[1, 2, 3, 4], target 1: 0
[0, 0, 1], target 1: 4

The first line matches the hand count of 5. The second matches the single subset {1, 3}. The third and fourth come from the range and parity tests. The compiler printed no warnings.

I also checked the function against a brute force program that tries all 2^n sign patterns, on 3000 random lists of up to 12 numbers, with values from 0 to 7 and targets from -20 to 20. The two programs agreed on every case.

Worked example 2: zeros double the count

A zero is a number too. Its sign does not change the total, so +0 and -0 give the same result. Each zero therefore doubles the number of sign patterns.

Take 0, 0, 1 and target 1. Each zero can be plus or minus, which gives 2 times 2 = 4 choices, and the 1 must be plus. All four patterns give 1, so the answer is 4. The program prints 4 for this input.

The code handles zeros without a special case. When x is 0, the loop body becomes ways[s] += ways[s], so every count doubles. The loop runs from P down to 0, so every entry doubles exactly once for each zero. The answer for 0, 0, 1 comes out right because the loop does this on its own.

Worked example 3: five numbers and a negative target

Take 1, 2, 3, 4, 5 and a target of 3. The total is 15, so T + target = 18. That is even, so P = 9. The subsets of these numbers that add to 9 are {4, 5}, {2, 3, 4} and {1, 3, 5}. Each subset gives one sign pattern, where the subset gets plus signs and the rest get minus signs.

Check one of them. For {2, 3, 4} the plus group is 2, 3, 4 and the minus group is 1, 5. The result is 2 + 3 + 4 - 1 - 5 = 3, which is the target.

Count all 32 sign patterns for these five numbers and you get 3 as well. The table walk is the same as in worked example 1, only longer, so the program does the walk for you.

Now a negative target. Take 2, 2, 2 and a target of -2. The total is 6, so T + target = 4, and P = 2. A subset that adds to 2 is one of the three 2s on its own. So there are three patterns, one plus and two minus in each: 2 - 2 - 2 = -2. The answer is 3. The code takes the absolute value of the target for the range test, and it uses the sum T + target for P. A negative target therefore needs no extra case.

Cost

Each number updates the P + 1 cells of the table once, so the time is about n * P steps for n numbers. The table takes P + 1 entries of memory. With 20 numbers and a total of 1000, that is at most about 20 thousand updates.

Trying every sign pattern takes 2^n patterns, and each pattern needs n additions. For 20 numbers that is about 20 million additions. The table is far less work when P is small compared with 2^n, which is the usual case for these problems. The table grows with the total, not with the number of sign patterns.

Common mistakes

Skipping the parity test

If you leave out the parity test, integer division rounds (T + target) / 2 down and the code still runs. For 1, 2, 3, 4 and target 1, (10 + 1) / 2 rounds down to 5, and the code counts the subsets that add to 5, which are {1, 4} and {2, 3}.

no parity check, [1,2,3,4] target 1 -> 2

The correct answer is 0. Keep the test if (want % 2 != 0) return 0; before the division.

Using the target as the subset sum

Some people set P = target. That is wrong. The subset sum is P = (T + target) / 2, which is the plus group. Using target gives the wrong count, because the minus group is not accounted for.

Walking the table upwards

If the inner loop goes upwards, ways[s - x] may already include the current number. The number is then counted twice.

forward count [1], P=2 -> 1

The correct answer is 0, because the list 1 has no subset that adds to P = 2. The upward walk used the same 1 twice, so the table reported one subset. Walk downwards.

Using int for the count

The count can grow fast. With 40 zeros and a target of 0 there are 2 to the power of 40 sign patterns, which is about one trillion. That does not fit in a 32-bit int, which stops at about 2 billion. Store the counts in long long (a 64-bit whole-number type), as the code above does.

Confusing the total with the plus group

The total T is the sum of every number, with no signs. The plus group P is the sum of only the plus numbers. The formula uses both, and mixing them up gives a target that is too big or too small.

Practice

Exercise 1

Count the sign patterns for 1, 1, 1, 1, 1 and target 1.

Show the answer

The total is 5 and the target is 1, so P = (5 + 1) / 2 = 3. The plus group must add to 3, so it holds three of the five 1s, and the minus group holds the other two. The result is 3 - 2 = 1, which is the target. Choosing 3 of the 5 numbers can be done in 10 ways, so the answer is 10.

Exercise 2

Count the sign patterns for 1, 2, 3 and target 6.

Show the answer

The total is 6 and the target is 6, so P = (6 + 6) / 2 = 6. The only subset that adds to 6 is all three numbers. So the answer is 1, which is the pattern +1 +2 +3.

Exercise 3

Why does 1, 2 have no sign pattern that gives 4?

Show the answer

The total is 3, and the target 4 is larger than 3. The biggest result any sign pattern can give is 1 + 2 = 3, so 4 cannot be reached. The range test returns 0 before any table is built.

Exercise 4

Why is the answer 0 for 1, 2, 3, 4 and target -1?

Show the answer

The total is 10 and the target is -1, so T + target = 9, which is odd. Every sign pattern gives an even result, so an odd target is impossible. The parity test returns 0.

Exercise 5

What is the answer for 0, 0, 1 with target -1? Explain the result without running the program.

Show the answer

The answer is 4. The zeros have no effect on the total, so each one can be plus or minus. The 1 must be minus, because the target is -1. There are 2 times 2 = 4 patterns, and all of them give -1.

Summary

• A plus or minus pattern with target target corresponds to a subset that adds to P = (T + target) / 2, where T is the total.
• Check the range first: if the absolute value of the target is more than T, the answer is 0.
• Check the parity next: if T + target is odd, the answer is 0.
• Count subsets with a table where each cell stores a count, and walk the inner loop downwards so each number is used once.
• Zeros double the count automatically, and the count needs long long for large inputs.