Target Sum

Difficulty: Medium Source: NeetCode

Problem

You are given an integer array nums and an integer target. Assign a + or - to each element of nums. Return the number of different ways you can assign symbols to make the sum of nums equal to target.

Example 1: Input: nums = [1,1,1,1,1], target = 3 Output: 5

Example 2: Input: nums = [1], target = 1 Output: 1

Constraints:

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• -1000 <= target <= 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

• Recursion / Backtracking — exploring all sign assignments
• Subset Sum — 0/1 knapsack variant
• Math reduction — converting the problem into a cleaner form

1. Brute Force / Recursive

Intuition

At each index, we can assign + or - to the current number. We recurse through all indices, accumulating the running total. When we reach the end, check if the total equals the target. This is O(2^n) since each element has two choices, but it’s simple and correct.

Algorithm

1. Define dfs(i, total) = number of ways to reach target using nums[i:] with current total.
2. Base: i == len(nums) → return 1 if total == target, else 0.
3. Return dfs(i+1, total + nums[i]) + dfs(i+1, total - nums[i]).

Solution

def findTargetSumWays(nums, target):
    def dfs(i, total):
        if i == len(nums):
            return 1 if total == target else 0
        return dfs(i + 1, total + nums[i]) + dfs(i + 1, total - nums[i])

    return dfs(0, 0)


print(findTargetSumWays([1, 1, 1, 1, 1], 3))  # 5
print(findTargetSumWays([1], 1))               # 1
print(findTargetSumWays([1], -1))              # 1
print(findTargetSumWays([0, 0, 0], 0))         # 8

Complexity

• Time: O(2^n)
• Space: O(n) — recursion depth

2. DP with Memoization (Top-Down)

Intuition

The brute force recomputes the same (i, total) pairs many times. Cache them. The total ranges from -sum(nums) to +sum(nums), so the state space is O(n * sum). Using a dictionary as a memo makes this clean.

Algorithm

1. Define dfs(i, total) with a memo dictionary.
2. If (i, total) is in memo, return it.
3. Otherwise compute recursively and cache.

Solution

def findTargetSumWays(nums, target):
    memo = {}

    def dfs(i, total):
        if i == len(nums):
            return 1 if total == target else 0
        if (i, total) in memo:
            return memo[(i, total)]
        result = dfs(i + 1, total + nums[i]) + dfs(i + 1, total - nums[i])
        memo[(i, total)] = result
        return result

    return dfs(0, 0)


print(findTargetSumWays([1, 1, 1, 1, 1], 3))  # 5
print(findTargetSumWays([1], 1))               # 1


# --- Math reduction to subset sum ---
# Let P = sum of positive subset, N = sum of negative subset.
# P + N = S (total sum)
# P - N = target
# => 2P = S + target => P = (S + target) / 2
# Count subsets of nums summing to P.
def findTargetSumWays_dp(nums, target):
    S = sum(nums)
    # If (S + target) is odd or out of range, no solution
    if (S + target) % 2 != 0 or abs(target) > S:
        return 0
    P = (S + target) // 2

    dp = [0] * (P + 1)
    dp[0] = 1

    for num in nums:
        for j in range(P, num - 1, -1):
            dp[j] += dp[j - num]

    return dp[P]


print(findTargetSumWays_dp([1, 1, 1, 1, 1], 3))  # 5
print(findTargetSumWays_dp([1], 1))               # 1
print(findTargetSumWays_dp([0, 0, 0], 0))         # 8

Complexity

• Time: O(n * sum(nums))
• Space: O(sum(nums))

Common Pitfalls

Forgetting the parity check. (S + target) must be even for a valid partition to exist. If it’s odd, the answer is immediately 0.

Not handling zeros. A zero can be assigned +0 or -0, both giving the same sum — they count as two different assignments. The subset-sum approach handles this naturally since dp[j] += dp[j - 0] adds dp[j] to itself.

Iterating the knapsack forward. This is a 0/1 knapsack (each number used once). Iterate j from P down to num, not forward — otherwise you reuse the same number multiple times.