Target Sum
Asked at Pinterest
Problem
Target Sum asks in how many ways you can put a + or - in front of each number so the expression equals a target. Brute force tries 2^n sign patterns; the elegant solution rewrites it as a subset-sum count and solves it with a 1D knapsack DP.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Pinterest questions → |
How to Think About It
Brute force recursion tries both signs for every number: O(2^n). Memoizing on (index, runningSum) brings it down to O(n * sum).
Key insight: split the numbers into a positive set P and a negative set N. Then sum(P) - sum(N) = target and sum(P) + sum(N) = total, so sum(P) = (target + total) / 2.
So the question becomes: how many subsets sum to (target + total) / 2? If target + total is odd or abs(target) > total, the answer is 0.
Count subsets with a 1D DP: dp[s] = number of ways to reach sum s. For each number x, iterate s from high to low and do dp[s] += dp[s - x] — iterating downward prevents reusing x.
Walkthrough for [1,1,1,1,1], target 3: total 5, subset target (3 + 5) / 2 = 4. Number of ways to choose four 1s from five = 5.
Optimal Approach
Step 1: total = sum(nums). If abs(target) > total or (target + total) is odd, return 0.
Step 2: goal = (target + total) // 2, dp = [1] + [0] * goal.
Step 3: For each x in nums: for s from goal down to x: dp[s] += dp[s - x].
Step 4: Return dp[goal].
Zeros are handled naturally: each zero doubles the count because dp[s] += dp[s - 0].
Time: O(n * goal). Space: O(goal).
What Trips People Up in Real Interviews
Iterating the inner loop upward. That lets a number be used more than once — it becomes an unbounded knapsack and overcounts.
Forgetting the parity and range checks. A negative or fractional goal means there is no solution.
Using a dp array indexed by the signed running sum without an offset — negative indices break.
Missing that zeros double the answer (+0 and -0 are different expressions). The DP handles it; a hand-rolled shortcut might not.
Solution Code
def findTargetSumWays(nums, target):
total = sum(nums)
if abs(target) > total or (target + total) % 2:
return 0
goal = (target + total) // 2
dp = [1] + [0] * goal
for x in nums:
for s in range(goal, x - 1, -1):
dp[s] += dp[s - x]
return dp[goal]Frequently Asked Questions
What is the Target Sum problem?
Target Sum asks in how many ways you can put a `+` or `-` in front of each number so the expression equals a target. Brute force tries `2^n` sign patterns; the elegant solution rewrites it as a subset-sum count and solves it with a 1D knapsack DP.
How do you solve Target Sum?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Target Sum?
Target Sum is asked at Pinterest. It is a medium difficulty problem.
What are common mistakes on Target Sum?
- Iterating the inner loop upward. That lets a number be used more than once — it becomes an unbounded knapsack and overcounts.
- Forgetting the parity and range checks. A negative or fractional `goal` means there is no solution.
- Using a `dp` array indexed by the signed running sum without an offset — negative indices break.
- Missing that zeros double the answer (`+0` and `-0` are different expressions). The DP handles it; a hand-rolled shortcut might not.