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
def findTargetSumWays(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. The branching doubles with every extra element, so this does not generalize.
Approach 2 — Top-down memoization
Two sign choices that reach the same index with the same running total lead to the same remaining subproblem. The state is the pair (i, total), and there are only O(n · sumRange) such states, so caching removes the redundant recomputation. Note how dfs(2, 0) below is reached along two different paths:
flowchart TD
A["dfs(0, 0)"] --> B["dfs(1, +1)"]
A --> C["dfs(1, -1)"]
B --> D["dfs(2, +2)"]
B --> E["dfs(2, 0)"]
C --> F["dfs(2, 0)"]
C --> G["dfs(2, -2)"]
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
def findTargetSumWays(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)
Let P be the numbers given a + and N the ones given a -. We need sum(P) - sum(N) = target. Since sum(P) + sum(N) = total, adding the two equations 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
def findTargetSumWays(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
Each row dp[i] reads only from dp[i-1], so one array suffices. 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
def findTargetSumWays(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.