Problem Statement
Target Sum
You get a list of numbers called nums and a goal number called target. In front of each number you must put a plus sign or a minus sign, then add it all up. The question is, how many different ways of choosing those signs give you a result equal to target. For example, with nums = [1, 1, 1, 1, 1] and target = 3, there are 5 ways to place the signs so the total is 3. Here is the clever trick. Split the numbers into two groups, one group that gets a plus sign (call its sum P) and one group that gets a minus sign (call its sum N). The final total is P minus N, which must equal target. Also P plus N is just the total of all the numbers, call it totalSum. If you add those two facts together you get 2P = target + totalSum, so P = (target + totalSum) / 2. That means the whole sign problem turns into a simpler one, count how many groups of numbers add up exactly to P.
Signals to notice
Brute force first
Try all 2^n sign assignments. Each number is either + or. giving binary choices. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
Transform: find a subset P where sum(P) = (totalSum + target) / 2. This reduces to subset sum counting. dp[j] += dp[j - num] for each number. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.
Trace it on nums=[1,1,1,1,1], target=3
Setup: total=5, (total+target)=8 even, new_target=(5+3)/2=4, dp=[1,0,0,0,0] num=1 (s:4..1): dp=[1,1,0,0,0] num=1: dp=[1,2,1,0,0] num=1: dp=[1,3,3,1,0] num=1: dp=[1,4,6,4,1] num=1: dp=[1,5,10,10,5] return dp[new_target]=dp[4]=5
What must stay true
If positive numbers sum to P and negatives to N, then P - N = target and P + N = totalSum. So P = (totalSum + target) / 2. Counting subsets with this sum counts the valid assignments. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Shape of the loop
new_target = (sum(nums) + target) / 2
dp = array of zeros, dp[0] = 1
for num in nums:
for s from new_target down to num: # iterate high->low for 0/1 knapsack
dp[s] += dp[s - num]
return dp[new_target]Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not seeing the reduction to subset sum — the +/- assignment can be split into a positive set and negative set, transforming the problem algebraically. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.