Example 1
ready- Input
nums = [ 1, 1, 1, 1, 1 ] target = 3- Expected
5- Why
- five different choices leave one 1 with a minus sign
Target Sum
35 min · findTargetSumWays()mediumOpen in LeetCode #494 ↗
The same list of numbers can tell very different stories once every value gets a plus or a minus sign.
Given non-negative integers nums and an integer target, place either + or -
before every array position. Return the number of distinct sign assignments whose final
sum equals target.
Positions stay distinct even when their values match. A zero has two sign choices too:
+0 and -0 produce the same sum, but they are different assignments and must both be
counted.
A few ground rules:
- Every position receives exactly one sign.
- You return a count, not one arrangement of signs.
- Every answer in the test suite is smaller than
2^31.
Constraints
1 <= nums.length <= 200 <= nums[i] <= 1_000-1_000 <= target <= 1_000- The answer is smaller than
2^31.
Hints
Write the honest search first
At each position you have two branches: add the value or subtract it. The pair
(position, running sum) captures everything the remaining choices need to know.
Two piles are hiding here
Let P be the sum of values given +, N the sum of values given -, and S the
sum of all values. Then P - N = target and P + N = S.
Count instead of mark
Solving those equations gives P = (S + target) / 2. Use a subset-sum table whose
cells store how many ways reach each sum, not just whether that sum is reachable.
Follow-up
How would you recover one valid sequence of signs when the returned count is nonzero?
Visible cases
Examples
Example 2
ready- Input
nums = [ 1 ] target = 1- Expected
1- Why
- +1 reaches the target
Example 3
ready- Input
nums = [ 1 ] target = 2- Expected
0- Why
- neither +1 nor -1 can reach 2
Interview signal
Asked at
AmazonGoogleMeta
The obvious decision tree has two branches per number. Its repeated states are your first route to DP; a little algebra then reveals a smaller counting DP.
Let S = sum(nums).
Memoized sign search
At index i, try both signs and add the counts returned by the two branches.
Memoization means caching the answer for each (i, running_sum) state; this is
top-down dynamic programming (DP) because identical suffix problems are solved once.
from functools import cache
def find_target_sum_ways(nums: list[int], target: int) -> int:
@cache
def count(i: int, running_sum: int) -> int:
if i == len(nums):
return int(running_sum == target)
value = nums[i]
return count(i + 1, running_sum + value) + count(
i + 1, running_sum - value
)
return count(0, 0)Notice what happens for zero: the two recursive calls ask the same cached question, but their returned counts are still added twice. That preserves the two distinct sign choices.
Time O(n · S) because each index can meet only sums between -S and S.
Space O(n · S) for the cached states and the recursion stack.
Subset-count DP
Split the positions into a plus group with sum P and a minus group with sum N:
P - N = target and P + N = S, so P = (S + target) / 2.
If target lies outside [-S, S], or S + target is odd, that subset sum can't exist.
Otherwise, let ways[s] count the subsets processed so far whose values total s.
def find_target_sum_ways(nums: list[int], target: int) -> int:
total = sum(nums)
if abs(target) > total or (total + target) % 2 == 1:
return 0
subset_target = (total + target) // 2
ways = [0] * (subset_target + 1)
ways[0] = 1
for value in nums:
for subtotal in range(subset_target, value - 1, -1):
ways[subtotal] += ways[subtotal - value]
return ways[subset_target]The backward scan enforces one use per position. When value == 0, each cell adds itself
to itself, exactly doubling every existing count.
Time O(n · S) in the worst case. Space O(S) for the one-row count DP.
The algebra doesn't replace the DP; it changes the DP state from signed running totals to one non-negative subset target.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
5
Run: visible + custom · Submit: full suite