MediumArrayDynamic ProgrammingBacktrackingUpdated Sep 2026

494. Target Sum

Asked at Pinterest

Difficulty

Medium

Time

O(n * goal)

Space

O(goal)

Pattern

Array

Companies

1

Problem

You get an array of integers nums and an integer target. For every number you must choose one sign, + or -, and write the numbers in order with those signs in front of them. This builds one expression.

Return how many different sign choices produce an expression whose value equals target. Two choices count as different if at least one number gets a different sign. The order of the numbers never changes.

The trick that makes this fast: let P be the numbers you give a + and N the numbers you give a -. Then sum(P) - sum(N) = target, and sum(P) + sum(N) = total (the sum of all numbers). Adding these gives sum(P) = (target + total) / 2. So the question becomes: how many subsets of nums add up to (target + total) / 2? If target + total is odd, or abs(target) > total, no subset can work and the answer is 0.

Pick a sign for every number

nums1111101234Five numbers, each one needs a sign in front of it+1 +1 +1 +1 -1 = 3+1 +1 +1 -1 +1 = 3... 5 patterns in totalOnly the patterns that add up to target 3 are counted
Each number gets + or -, and we count the sign patterns whose total equals target.

Constraints

  • ●1 <= nums.length <= 20
  • ●0 <= nums[i] <= 1000
  • ●0 <= sum(nums[i]) <= 1000
  • ●-1000 <= target <= 1000

Examples

Example 1
Inputnums = [1,1,1,1,1], target = 3
Output5
Whytotal = 5, so the positive subset must sum to (3 + 5) / 2 = 4. Any four of the five 1s give 4, and there are 5 ways to pick which one is left out. Each pick is one valid sign pattern.
Example 2
Inputnums = [1], target = 1
Output1
Whytotal = 1, so the positive subset must sum to (1 + 1) / 2 = 1. Only the subset {1} works, giving the single expression +1.

Asked At

1 companies
CompanyDifficulty
PinterestMediumView all Pinterest questions →

How to Think About It

1

Brute force recursion tries both signs for every number: O(2^n). Memoizing on (index, runningSum) brings it down to O(n * sum).

2

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.

3

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.

4

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.

5

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).

Turn it into a subset-sum count

numssum = 41111101234total = 5, so the + subset must sum to (3 + 5) / 2 = 4dp01234ways11111After all five 1s, dp[4] = 5 ways to reach sum 4goal = (target + total) / 2dp[s] += dp[s - x] (s high → low)
Choosing which numbers get + is the same as choosing a subset that sums to 4.
ComplexityTime O(n * goal)Space O(goal)goal = (target + total) / 2, and the cost comes from looping over every number and every reachable subset sum up to goal.

What Trips People Up in Real Interviews

1

Iterating the inner loop upward. That lets a number be used more than once — it becomes an unbounded knapsack and overcounts.

2

Forgetting the parity and range checks. A negative or fractional goal means there is no solution.

3

Using a dp array indexed by the signed running sum without an offset — negative indices break.

4

Missing that zeros double the answer (+0 and -0 are different expressions). The DP handles it; a hand-rolled shortcut might not.

Solution Code

O(n * goal) time
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]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

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 runs in O(n * goal) time and O(goal) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.