Target Sum — InterviewPrepKit

Solving tips

Algebraic reduction is the key insight: with P the added set and N the subtracted set, sum(P)-sum(N)=target and sum(P)+sum(N)=total give sum(P)=(target+total)/2, turning this into 'count subsets summing to that value'.
Add the feasibility guard first: if abs(target)>total or (total+target) is odd, return 0 before dividing.
Then it is a counting 0/1 knapsack: dp[s] += dp[s-num]; with the 1-D array sweep s DESCENDING so each number is used at most once per row.
Pitfall: don't optimize away zeros — a 0 can take + or - and legitimately doubles the count, which the subset-sum formulation handles automatically. Target O(n*subset) time.

Problem

You are given an integer array nums and an integer target. You must place either a + or a - in front of every number in nums, then concatenate them into an arithmetic expression and evaluate it. Count how many distinct sign assignments make the expression evaluate exactly to target.

Each element must receive a sign, order is fixed, and two assignments are different if any single element’s sign differs.

Examples

nums = [1,1,1,1,1], target = 3 → 5 — you must flip exactly one number to -; there are 5 choices of which one.
nums = [1], target = 1 → 1 — only +1 works.
nums = [1], target = 2 → 0 — neither +1 nor -1 reaches 2.

Constraints

1 <= len(nums) <= 20
0 <= nums[i] <= 1000
0 <= sum(nums) <= 1000
-1000 <= target <= 1000
With up to 20 elements there are 2^20 ≈ 10^6 sign patterns — brute force is borderline, but the bounded sum invites a knapsack-style table.

Think about it first

Hint 1

Every element is either added or subtracted. Split `nums` into the set `P` of numbers you add and the set `N` of numbers you subtract. Then `sum(P) - sum(N) = target` and `sum(P) + sum(N) = sum(nums)`.

Hint 2

Adding those two equations, `2·sum(P) = target + sum(nums)`, so `sum(P) = (target + total) / 2`. The problem becomes: how many subsets of `nums` sum to that fixed value? That is a counting knapsack.

Hint 3

Let `dp[i][s]` be the number of ways to pick from the first `i` numbers so they sum to `s`. Each new number is either taken or skipped: `dp[i][s] = dp[i-1][s] + dp[i-1][s - nums[i-1]]`. Because each row depends only on the previous row, one rolling array suffices.

TL;DR

Reduce to “count subsets summing to (target + total) / 2” and fill a counting-knapsack table — O(n · P) time, O(P) space with a rolling row, where P is that subset sum.

Approach 1 — Brute force recursion

Try both signs at every index and count the leaf paths that land on target.

from typing import List

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        def dfs(i: int, total: int) -> int:
            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)

Complexity: O(2^n) time, O(n) recursion depth. With n = 20 that is ~10^6 leaves — it squeaks by here, but the branching doubles with every extra element, so it does not generalize.

Approach 2 — Top-down memoization

The insight: two different sign choices that reach the same index with the same running total have identical futures. The state is the pair (i, total), and there are only O(n · sumRange) such states, so caching collapses the exponential tree.

State / recurrence. dfs(i, total) = number of ways to sign nums[i:] so the remaining suffix drives total up to target. Transition: dfs(i, total) = dfs(i+1, total + nums[i]) + dfs(i+1, total - nums[i]); base case dfs(n, total) = [total == target].

from typing import List
from functools import lru_cache

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        @lru_cache(maxsize=None)
        def dfs(i: int, total: int) -> int:
            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)

Complexity: O(n · S) time and space, where S is the span of reachable sums (≤ 2·total + 1).

Approach 3 — Bottom-up counting knapsack (the 2-D table)

The insight: with P = the numbers given a + and N the ones given a -, we need sum(P) - sum(N) = target. Since sum(P) + sum(N) = total, adding gives sum(P) = (target + total) / 2. If that value is not a non-negative integer, the answer is 0. Otherwise count subsets of nums that sum to subset = (target + total) / 2.

State / recurrence. dp[i][s] = number of subsets of the first i numbers that sum to exactly s. Each nums[i-1] is either skipped or taken:

dp[i][s] = dp[i-1][s]                      # skip nums[i-1]
         + dp[i-1][s - nums[i-1]]          # take it, if s >= nums[i-1]

Base row dp[0][0] = 1 (the empty subset sums to 0), dp[0][s>0] = 0.

from typing import List

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if abs(target) > total or (total + target) % 2 != 0:
            return 0
        subset = (total + target) // 2
        n = len(nums)
        dp = [[0] * (subset + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        for i in range(1, n + 1):
            num = nums[i - 1]
            for s in range(subset + 1):
                dp[i][s] = dp[i - 1][s]
                if s >= num:
                    dp[i][s] += dp[i - 1][s - num]
        return dp[n][subset]

Walkthrough with nums = [1,1,1,1,1], target = 3: total = 5, so subset = (5 + 3) / 2 = 4. We count subsets of five 1’s summing to 4 — that means choosing 4 of the 5 ones (the chosen ones get +, the leftover single 1 gets -, yielding 4 - 1 = 3). There are C(5,4) = 5 such subsets, and dp[5][4] fills to 5.

Complexity: O(n · subset) time, O(n · subset) space.

Approach 4 — Space-optimized rolling row

The insight: dp[i] reads only from dp[i-1]. Keep one array and iterate s downward so each number is counted at most once per row (a right-to-left sweep prevents reusing nums[i-1] twice within the same iteration).

from typing import List

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if abs(target) > total or (total + target) % 2 != 0:
            return 0
        subset = (total + target) // 2
        dp = [0] * (subset + 1)
        dp[0] = 1
        for num in nums:
            for s in range(subset, num - 1, -1):
                dp[s] += dp[s - num]
        return dp[subset]

Complexity: O(n · subset) time, O(subset) space.

Common pitfalls

Forgetting the parity/feasibility guard: if (total + target) is odd or abs(target) > total, no assignment works — return 0 before dividing.
Iterating the 1-D array left to right, which double-counts a number and inflates the answer; the 0/1 knapsack demands a descending sweep.
Zeros in nums matter: a 0 can take a + or - and still contribute nothing, so it legitimately doubles the count. The subset-sum formulation handles this automatically — do not “optimize” zeros away.
Assuming target can be negative-only special-cased; the transform subset = (total + target)/2 already covers negative targets.

Pattern takeaway

When a problem asks you to count the ways to hit an exact value by including/excluding items, reach for the counting knapsack: dp[i][s] over “first i items” and “target sum s”, with the take-or-skip recurrence dp[i][s] = dp[i-1][s] + dp[i-1][s-w]. A clever algebraic reduction (here, splitting into + and - sets) often turns an unfamiliar phrasing into this canonical 2-D table, which then collapses to a single rolling row swept right-to-left.