Target sum by transforming to subset sum in Python

Why this matters

A game gives points for some events and takes points away for others. A bank statement adds some payments and subtracts others. In both cases a programmer may ask: how many ways can the signs be chosen so that the final number is exactly a target? The answer tells you how many outcomes lead to the target, which is useful for testing a scoring rule or checking a budget.

Trying every sign choice works, but it grows fast. With n numbers there are 2 to the power n sign choices. This lesson turns the sign question into a subset question. The subset question is solved with a counting table, which is a dynamic programming (DP) method: a small answer is stored in a table and reused for bigger answers.

The previous lesson in this module, Partition into equal subsets with Python int bit rows, asked a yes or no question about subsets. This lesson asks how many subsets fit, so the table holds counts instead of True and False.

Words you need first

A sign is the plus or minus in front of a number. In +1 +1 -1, the signs are plus, plus and minus.

An expression is the whole line of signed numbers, such as +1 +1 -1. Its value is the result, which is 1 here.

A subset is a group of the numbers you pick. The empty subset is allowed.

Parity means whether a whole number is even or odd. A number is even when it can be divided by 2 with no remainder. Parity is the first thing to check in this lesson.

Absolute value is a number's distance from zero, ignoring the sign. The absolute value of -7 is 7. Python writes it as abs(-7).

The problem in small form

Take five ones: [1, 1, 1, 1, 1] and target 3. One way to reach 3 is +1 +1 +1 +1 -1, which gives 4 - 1 = 3. The minus sign can go on any one of the five numbers, so there are five ways in total. The other sign choices give 1, 5 or other values.

A program can test every sign choice. Each choice is a row of plus and minus signs, and there are 2 to the power 5 = 32 rows for five numbers. The program below does exactly that. It also counts the same answers with the method from the next steps, so you can compare them.

Its output is:

nums [1, 1, 1, 1, 1] target 3
  brute force: 5
  subset sum:  5
nums [0, 0, 1] target 1
  brute force: 4
  subset sum:  4
nums [1, 2, 3] target 0
  brute force: 2
  subset sum:  2
nums [1, 2, 3, 4, 5] target 3
  brute force: 3
  subset sum:  3

The brute force column is the ground truth. The subset sum column matches it on all four lists. The next steps explain why.

The program uses (mask >> i) & 1 to read bit i of mask. That is the same bit-reading idea from the previous lesson. The line total += x if ... else -x picks x or -x in one expression.

Step 1: turn the signs into two groups

Split the numbers into two groups. The plus group has a sum we call P. The minus group has a sum we call N. The total of all numbers is S, so S = P + N.

The value of the expression is the plus group minus the minus group: P - N. We want that to equal the target:

• P - N = target
• P + N = S

Add the two lines. The N terms cancel, leaving 2P = S + target. So:

P = (S + target) / 2

This is the key step. Choosing which numbers get a plus sign is the same as choosing a subset that adds up to P. The numbers not in the subset get minus signs, and their sum is then S - P, so the expression value is P - (S - P) = 2P - S = target.

For [1, 1, 1, 1, 1] with target 3: S = 5, so P = (5 + 3) / 2 = 4. The question becomes: how many subsets of the five ones add up to 4? Choosing any four of the five ones gives such a subset, which gives 5. That matches the brute force answer.

Each subset gives exactly one sign pattern, and each sign pattern gives exactly one subset. So the two counts are equal.

In the code, the formula is written with //, which is integer division. It gives a whole number. The parity check in the next step makes sure the division is exact.

Step 2: check parity and range first

The formula P = (S + target) / 2 only makes sense when S + target is even. P is a sum of whole numbers, so it is a whole number, and 2P is always even. If S + target is odd, no sign pattern can produce the target, and the answer is 0.

Here is an example. The list [1, 1, 1, 1, 1] has total 5. Target 2 gives S + target = 7, which is odd. Five numbers that are each plus or minus 1 always add to an odd number, so 2 cannot be reached. The answer is 0.

A second check is abs(target) > total. If the target is bigger than the total, even the largest possible sum is too small. In that case the answer is also 0, and the program returns early. This check also keeps P from going negative, which the mistakes section shows.

The count_ways function in the program above does both checks before it builds the list.

Step 3: count, do not just check

The previous lesson used a table of true and false values. This lesson needs a count, so the list holds numbers. Cell s holds the number of subsets whose sum is exactly s.

Start with ways[0] = 1, because the empty subset has sum 0 and there is exactly one of it. Every other cell starts at 0.

For each number x, a subset that sums to s can be built in two ways. It can leave x out, which keeps the count ways[s]. Or it can include x, which means a subset that sums to s - x already existed. So the new count is the old count plus ways[s - x]:

ways[s] = ways[s] + ways[s - x]

As in the previous lesson, the inner loop runs backwards from p down to x. Then ways[s - x] still holds its value from before this number was processed, so each number is used at most once.

Here is a trace for [1, 1, 1, 1, 1] with p = 4. The program prints the whole list after each number.

Its output is:

start:   [1, 0, 0, 0, 0]
after 1: [1, 1, 0, 0, 0]
after 1: [1, 2, 1, 0, 0]
after 1: [1, 3, 3, 1, 0]
after 1: [1, 4, 6, 4, 1]
after 1: [1, 5, 10, 10, 5]
ways[4] = 5
ways[3] (the target used as P, wrong) = 10

Each row is the count list after one more number. After the first number, there is one subset with sum 0 and one with sum 1. After the second number, there are two subsets with sum 1, and so on. The last row shows that 5 subsets sum to 4, which is the answer. The numbers in each row are the binomial coefficients, which count the ways to choose k items out of n, but you do not need that fact to use the table.

The program also shows why the target must be converted first. Using the target 3 directly gives 10, which is the number of subsets that sum to 3. That is not the answer, because P must be 4 for this target.

Step 4: zeros and longer lists

A zero in the list is a useful test case. A zero can be given a plus or a minus sign, and both choices give the same value. So each zero doubles the count. The list method handles this without a special case.

Take [0, 0, 1] with target 1. The total is 1 and P = (1 + 1) / 2 = 1. The subsets that sum to 1 are {1}, {0, 1} (first zero), {0, 1} (second zero) and {0, 0, 1}. That is 4 subsets. In the list method, each zero runs the update ways[s] += ways[s] for the cells it touches, which doubles the counts. The brute force program gives 4 too.

The list [1, 2, 3, 4, 5] with target 3 is longer. Its total is 15, so P = (15 + 3) / 2 = 9. The subsets that sum to 9 are 4, 5, 2, 3, 4 and 1, 3, 5. That is 3, which matches the program. Each one gives one expression. For example 1, 3, 5 as the plus group gives +1 -2 +3 -4 +5 = 3.

The list method takes about n * p steps, where n is the number of items and p is the sum it counts up to. The brute force method takes about 2 to the power n steps. With 20 numbers, the brute force needs about one million sign patterns. A table that counts up to a small p is faster, but a large total makes the list large. Compare n, the total and the target before you choose.

Step 5: targets below zero

A negative target uses the same formula. Only the value of P changes. For the target -4 the formula gives a smaller P than for +4, but the method is the same.

There is also a symmetry. If you flip every sign in a valid expression, the value changes sign. So the number of ways to reach -t equals the number of ways to reach t. Take the list [2, 3, 4, 7], which has total 16. The target 4 has one way: +3 +7 -2 -4. Flipping every sign gives -3 -7 +2 +4, which is the target -4. The program below prints the counts for targets from -4 to 4 and checks the symmetry for targets 0 to 16.

Its output is:

nums: [2, 3, 4, 7] total 16
target -4: 1 ways, brute force 1
target -3: 0 ways, brute force 0
target -2: 2 ways, brute force 2
target -1: 0 ways, brute force 0
target 0: 0 ways, brute force 0
target 1: 0 ways, brute force 0
target 2: 2 ways, brute force 2
target 3: 0 ways, brute force 0
target 4: 1 ways, brute force 1
count(target) equals count(-target) for targets 0 to 16: True

A count of 0 is correct here. For target 0 the plus group would need to sum to 8, and no subset of [2, 3, 4, 7] does. Use the symmetry as a check on your own program.

The all(...) call checks the condition for every value in the range and returns True only when every check passes. It is shorter than a loop with a flag variable.

Step 6: check the method against brute force

The checks above used four lists. A better test is to compare the two methods on many random lists. The next program does that for 3000 random lists of up to 10 numbers. The numbers range from 0 to 9, and the targets range from -30 to 30. It also prints the number of lists that have at least one way.

Its output is:

checked 3000 random cases, 773 had at least one way

All 3000 cases agree. The 2227 cases that gave 0 are the ones where the target is out of range or has the wrong parity, plus the cases where the signs simply cannot reach the target. The brute force check is the reason to trust the list method. Write this kind of check whenever you change a counting program.

Common mistakes

Skipping the parity check

Without the parity check, the division quietly rounds the value of P down. This program skips the check for the list of five ones and target 2:

Its output is:

total 5, target 2, (total + target) is odd
subsets summing to 3 without the check: 10
correct answer: 0 (five +1 or -1 signs always add to an odd number)

The program reports 10 subsets, which would be a wrong answer. The correct answer is 0. The check (total + target) % 2 != 0 must run before the division.

A target that is too negative

If the target is far below minus the total, P becomes negative. With the five ones and target -9, the formula gives (5 + -9) // 2, which is -2. Then [0] * (p + 1) builds an empty list, because multiplying a list by a negative number gives an empty list. The next line tries to set ways[0], which does not exist, so Python stops with this error:

ways = [0] * (-2 + 1)
ways[0] = 1   # IndexError: list assignment index out of range

Running that code prints a traceback. The last line of the traceback reads:

IndexError: list assignment index out of range

The fix is the range check abs(target) > total from count_ways. It returns 0 before the list is built.

Using / instead of //

In Python 3, / gives a float. (total + target) / 2 for the five ones and target 2 is 3.5. That is not a whole number, and a list cannot be built with a float size. Use // for P, and run the parity check first so that the division is always exact.

Counts that get very large

Python ints do not overflow. A count that would wrap around in a 32-bit or 64-bit integer is stored exactly. With 40 ones and target 0, P is 20, and the count is the number of ways to choose 20 items from 40:

Its output is:

count: 137846528820
comb(40, 20): 137846528820

The two numbers match, and the count is exact. Python does not need a special 64-bit type for this. The cost of very large counts is time and memory, not wrong answers.

Using the target instead of P

It is easy to search for subsets that sum to the target itself. For the five ones with target 3, that gives 10 subsets, but the answer is 5. The P value from the formula must be used. The program in Step 3 prints both numbers so you can see the difference.

Practice

Exercise 1. Count the sign patterns for the list [2, 2, 2] with target 2.

Show the answer

The total is 6, and S + target = 8 is even, so P = 4. The subsets of [2, 2, 2] that sum to 4 are any two of the three 2s, which gives 3. The sign patterns are +2 +2 -2, +2 -2 +2 and -2 +2 +2. Each gives 2. The answer is 3.

Exercise 2. Can the list [1, 2, 3] reach the target 1? Give the answer without the program.

Show the answer

The total is 6 and the target is 1, so S + target = 7, which is odd. The parity check gives 0. The answer is no way.

Exercise 3. Count the sign patterns for the list [5] with target 0.

Show the answer

The total is 5 and the target is 0, so S + target = 5 is odd. The answer is 0. A single 5 can only give +5 or -5, and neither is 0.

Exercise 4. Count the sign patterns for the list [0, 3] with target 3.

Show the answer

The total is 3, so P = (3 + 3) / 2 = 3. The subsets that sum to 3 are {3} and {0, 3}, which gives 2. The sign patterns are +0 +3 and -0 +3. Both give 3. The answer is 2.

Exercise 5. Explain in your own words why the formula P = (S + target) / 2 turns the sign problem into a subset problem.

Show the answer

Each number is either in the plus group or the minus group. The value of the expression is the plus total minus the minus total. Since the two groups together add up to S, the value depends only on the plus total P. Fixing P to (S + target) / 2 means choosing a subset whose sum is P. Each subset is one sign pattern, so counting subsets counts sign patterns.

Summary

• Splitting the numbers into a plus group with sum P and a minus group turns a signs problem into a subset problem with P = (S + target) / 2.
• Check parity first: if S + target is odd, or the absolute value of the target is larger than the total, the answer is 0.
• Use a counting list. Loop backwards with range(p, x - 1, -1) so each number is used once.
• Zeros double the count, and the list method handles this with no special case.
• Test the method against brute force on random inputs before you trust it.