Target Sum hands you a list of non-negative integers and a target, and asks how many ways you can put a plus or a minus in front of every number so that the signed total equals the target. With five ones and a target of 3 the answer is 5: pick which single one gets the minus sign. The problem looks like a search puzzle, and a search does solve it, but only for tiny inputs. The interesting part is a two-line piece of algebra that turns it into a counting version of subset sum, which a one-dimensional table solves in time proportional to the number of elements times half the total.
This article starts from an exhaustive reference implementation, moves to a table over running totals, derives the reduction and its parity and bounds checks, then covers what most write-ups skip: zeros, overflow, recovering an assignment, values too large for a table, and testing. Every snippet was checked against brute force on thousands of random inputs. If dynamic programming is new to you, read dynamic programming from first principles first.
The problem, precisely
Input: an array nums of n non-negative integers and an integer target. Output: the number of sign vectors (s1, ..., sn), each si in {+1, -1}, with the sum of si times nums[i] equal to target. Two details decide correctness. Assignments are counted by position, not value, so two equal numbers with swapped signs are two assignments. And a zero contributes +0 and -0, so every zero doubles the answer. Deduplicating by value, or giving zero one sign, fails exactly the inputs a test suite should contain.
Let S be the sum of all elements. Every signed total lies between -S and S, so any target with |target| greater than S has zero ways. Interview constraints (n up to 20, sum up to 1,000) let several approaches work; real uses, such as checking whether ledger entries can net to a figure, need the one that survives larger inputs.
Brute force: the reference you keep
There are 2n sign vectors, so the simplest correct program enumerates them. It is exponential and useless beyond n of about 25, but it is the oracle every faster version is tested against, which makes it worth writing first and keeping in the test file.
import itertools
def brute(nums, target):
return sum(
1
for signs in itertools.product((1, -1), repeat=len(nums))
if sum(s * x for s, x in zip(signs, nums)) == target
)Written recursively (at index i with running total t, try both signs), the call tree has 2n leaves but only ever visits pairs (i, t) with t between -S and S, at most n times (2S + 1) of them. Caching each pair gives a memoised recursion in O(n S) time; its recursion depth of n breaks Python's default limit near a thousand, and its keys can be negative, which is why the bottom-up table below adds an offset.
The offset table: tabulating running totals
Shift every running total by S so it becomes an index between 0 and 2S. Let dp[j] be the number of ways to reach running total j - S using the elements processed so far. Start with dp[S] = 1 (the empty prefix has total 0), and for each element push every reachable total both up and down by x into a fresh array.
def offset_table(nums, target):
S = sum(nums)
if abs(target) > S:
return 0
width = 2 * S + 1
dp = [0] * width
dp[S] = 1 # running total 0 lives at index S
for x in nums:
nxt = [0] * width
for j, ways in enumerate(dp):
if ways:
if j + x < width:
nxt[j + x] += ways
if j - x >= 0:
nxt[j - x] += ways
dp = nxt
return dp[target + S]This runs in O(n times S) time and O(S) memory. It is the version to use if inputs may be negative (replace S with the sum of absolute values), and its final row answers every target at once. Its weakness is the constant factor: 2S + 1 cells and a new row per element.
The reduction to counting subsets
Split the elements by sign. Let P be the sum of the elements that get a plus and N the sum of those that get a minus. Two equations hold for every assignment: P - N = target, because that is the requirement, and P + N = S, because every element is in exactly one group. Adding them gives 2P = S + target, so P = (S + target) / 2.
That is the whole trick: choosing signs is choosing which subset gets the plus, and a subset works exactly when its sum is (S + target) / 2. Two guards fall out. If S + target is odd, P is not an integer and there are no solutions. If |target| exceeds S, P falls outside 0..S. Check |target|, not target: a very negative target makes P negative, and a negative index in Python silently reads from the end of the list.
The reduction needs non-negative elements, since P and N are sums of magnitudes; with negatives, use the offset table. Flipping every sign shows the count for target equals the count for -target, so counting the minus group with (S - target) / 2 gives the same answer.
The backwards one-dimensional loop
Counting subsets with a given sum is the 0/1 knapsack recurrence with addition in place of max. Let dp[s] count subsets of the elements seen so far that sum to s, starting from dp[0] = 1. Each subset either excludes x (count unchanged) or includes it (count from dp[s - x] before x). Iterating s from high to low lets one array serve as both rows, because dp[s - x] has not been touched yet in this pass.
def find_target_sum_ways(nums, target):
S = sum(nums)
if abs(target) > S or (S + target) % 2:
return 0
P = (S + target) // 2
dp = [0] * (P + 1)
dp[0] = 1
for x in nums:
for s in range(P, x - 1, -1): # high to low: each element used at most once
dp[s] += dp[s - x]
return dp[P]Iterate upwards and the same element can be counted several times in one pass, which silently turns the problem into the unbounded knapsack (coin change) and inflates the answer. In Java or C++, also choose the count type: the answer can reach 2n, so a 32-bit int overflows once n passes 30 and a 64-bit long once n passes 62. Use long[] dp when the answer is bounded, a modulus when the problem asks for one, and BigInteger otherwise.
Time is O(n times P) and memory O(P), with P at most S: roughly a quarter of the offset table's cells, with no per-element allocation.
Worked example
Take nums = [2, 3, 1, 4] and target 2: S = 10, S + target = 12 is even, so P = 6. Processing 2 adds dp[0] into dp[2]. Processing 3 walks s from 6 down: dp[5] picks up dp[2] and dp[3] picks up dp[0]. Processing 1 makes dp[3] = 2, since {3} and {2, 1} both sum to 3. Processing 4 adds dp[2] into dp[6], so dp[6] = 2. The two subsets are {2, 4} and {2, 3, 1}, which correspond to +2 -3 -1 +4 and +2 +3 +1 -4; both total 2.
For five ones and target 3, P = 4 and the rows are Pascal's triangle, ending at [1,5,10,10,5]; dp[4] = 5 is 5 choose 4, the ways to pick which four ones are positive.
Zeros, bounds and other edge cases
- Zeros. For x = 0 the loop runs s from P down to 0 and executes dp[s] += dp[s], doubling every cell. That is exactly the factor of two a zero contributes, so the reduced solution handles zeros without special cases. Test it: [0, 0, 1] with target 1 has four ways.
- Target out of range. Guard with |target| > S before computing P. Without the absolute value, target = -1000 against S = 10 gives a negative P and either an exception or a wrong index.
- Parity. An odd S + target means no subset can work; returning 0 early also avoids integer division silently rounding to a wrong P.
- Empty input. Exactly one (empty) assignment, which counts only when target is 0; the code returns 1 or 0 accordingly.
Recovering an assignment
To show which entries net to a figure you need a sign vector, not a count. Keep a 2-D table, reach[i][s] true if some subset of the first i elements sums to s, and walk back from (n, P): if reach[i - 1][s] holds, element i gets a minus; otherwise it gets a plus and s drops by its value.
def one_assignment(nums, target):
S = sum(nums)
if abs(target) > S or (S + target) % 2:
return None
P = (S + target) // 2
n = len(nums)
reach = [[False] * (P + 1) for _ in range(n + 1)]
reach[0][0] = True
for i, x in enumerate(nums, 1):
for s in range(P + 1):
reach[i][s] = reach[i - 1][s] or (s >= x and reach[i - 1][s - x])
if not reach[n][P]:
return None
signs, s = [], P
for i in range(n, 0, -1):
if reach[i - 1][s]:
signs.append("-")
else:
signs.append("+")
s -= nums[i - 1]
return signs[::-1]This costs O(n times P) memory, which is the price of reconstruction. To enumerate all solutions, branch at every step where both choices are feasible, the same backtracking pattern used in grid word search; the feasibility table prunes every dead branch, so the work is proportional to the output size plus the table.
When the table is too big: meet in the middle
The dynamic programs are pseudo-polynomial: cost grows with the values, not just their count. With 40 elements near a billion each, P is in the tens of billions and no table fits; counting subset sums is #P-hard in general. For small n with large values, enumerate the signed totals of each half with multiplicities (2n/2 each) and, for every left total t, count right totals equal to target - t.
from collections import Counter
def half_sums(xs):
sums = Counter({0: 1})
for x in xs:
nxt = Counter()
for s, c in sums.items():
nxt[s + x] += c
nxt[s - x] += c
sums = nxt
return sums
def meet_in_middle(nums, target):
mid = len(nums) // 2
left, right = half_sums(nums[:mid]), half_sums(nums[mid:])
return sum(c * right.get(target - s, 0) for s, c in left.items())At n = 40 that is about a million entries per side instead of a trillion leaves. Exponential state spaces are also tamed by DP over subsets, as in the travelling salesman DP. For reasoning about which regime you are in, Big-O analysis covers why n times S and 2n/2 behave so differently as inputs grow.
Testing it
Property-test every version against brute force on random small inputs: lengths 1 to 10, values 0 to 6 so zeros and duplicates are common, and targets beyond both -S and S. A few thousand cases run in under a second and catch the upward loop, a missing parity check and a wrong bound. Add fixed cases (five ones and 3 gives 5; [0, 0, 1] and 1 gives 4), and for reconstruction assert the signs sum to the target and None appears exactly when the count is zero.
Failure modes
| Symptom | Cause | Fix |
|---|---|---|
| Answer too large | Inner loop runs upwards, reusing an element | Iterate s from P down to x |
| Wrong answer when zeros are present | Zeros skipped or deduplicated | Let the loop double counts; never deduplicate input |
| IndexError or silent wrong value for negative targets | Bound checked on target, not |target| | Check abs(target) > S before computing P |
| Non-zero answer when S + target is odd | Integer division rounded P | Return 0 on odd parity |
| Negative or tiny counts in Java | int overflow past 2^31 | Use long, a modulus, or BigInteger |
| Memory error | Values large, so P is huge | Meet in the middle, or bitset reachability for yes/no |
Trade-offs
| Approach | Time | Memory | Use when |
|---|---|---|---|
| Brute force | O(2^n n) | O(n) | Tests and n up to about 20 |
| Offset table | O(n S) | O(S) | Negative elements, or all targets at once |
| Subset-count 1-D DP | O(n P) | O(P) | The default for non-negative inputs |
| Meet in the middle | O(2^(n/2)) | O(2^(n/2)) | n up to about 40 with large values |
What to do next
- Write the brute-force enumerator and keep it in your test file as the oracle.
- Implement the reduced solution with both guards: return 0 when |target| exceeds S or when S + target is odd.
- Run a random property test against the oracle, with zeros, duplicates and out-of-range targets in the generator.
- Choose the count type deliberately: long, a modulus, or arbitrary precision.
- If you need the signs themselves, keep the 2-D reachability table and backtrack from (n, P).
- Estimate P before running in production; if it is in the billions, switch to meet in the middle or rethink the problem.
- Practise choosing DP states on a different shape of problem, such as the longest palindromic subsequence.