Target Sum
You get an array nums of non-negative integers and an integer target. Put a plus or a minus sign in front of every number, keep their order, and evaluate the expression. Return how many sign choices make the expression equal target. Every one of the 2^n choices counts on its own, so +0 and -0 are two different choices.
Function
- numsinteger-array
- the numbers, each of which gets a sign
- targetinteger
- the value the expression must equal
- Returnsinteger
- the number of sign choices whose expression equals target
Constraints
1 ≤ nums.length ≤ 200 ≤ nums[i] ≤ 1000- The sum of
numsis at most 1000. -1000 ≤ target ≤ 1000- The answer is at most 220, well inside a 32-bit signed integer.
Examples
- Input
- nums = [2, 1, 1]target = 2
- Output
- 2
- Explanation
+2 +1 -1and+2 -1 +1both equal 2. With a minus on the 2, the most you can reach is -2 + 1 + 1 = 0, so no other choice works.
- Input
- nums = [0, 4, 4]target = 0
- Output
- 4
- Explanation
- The two 4s need opposite signs,
+4 -4or-4 +4, and in both cases the 0 can take either sign. That makes 2 × 2 = 4 choices.
- Input
- nums = [6, 3]target = 4
- Output
- 0
- Explanation
- The four possible values are 9, 3, -3 and -9. Flipping a sign changes the total by twice that number, so every result is odd like 6 + 3 = 9, and the even target 4 is never reached.
Follow-up
Can you handle up to 40 numbers with values up to 10^9, where no array indexed by the sum fits in memory?
Hints
Open them one at a time. Each one gives away a little more.
You could try both signs for every number, which is
2^nexpressions. Notice that many different sign prefixes lead to the same running total, and from then on they behave exactly alike.Call
Pthe sum of the numbers that get a plus andNthe sum of the numbers that get a minus. You knowP - N = targetandP + N = sum(nums). What does that tell you aboutP?P = (sum + target) / 2, so count the subsets ofnumsthat add up to that value. Keepways[s], the number of subsets that reachs, and update it for each number from the largestsdown. Return 0 at once whensum + targetis odd or|target| > sum.
Solution
Each number has two signs, so there are 2^n expressions. Counting by position and running total merges sign prefixes that reach the same total. Better still, the plus-signed numbers form a subset with a fixed sum, so the problem becomes counting subsets with a given sum, in O(n × S) time where S is the sum of nums.
Try both signs for every number
Correct, but does not finish on the largest tests
Intuition
Walk the numbers left to right with a running total and branch twice at each one: add it, or subtract it. When every number has a sign, count 1 if the total equals target. Each sign choice is exactly one path, so the counts add up to the answer.
That is one leaf per choice: 2^20 ≈ 10^6 leaves for 20 numbers, and every extra number doubles the work.
Algorithm
- Write
count(i, total), the number of ways to signnums[i..]when the numbers beforeialready sum tototal. - If
i == n, return 1 whentotal == target, else 0. - Otherwise return
count(i+1, total + nums[i]) + count(i+1, total - nums[i]). - The answer is
count(0, 0).
def findTargetSumWays(nums, target):
n = len(nums)
def count(i, total):
# Ways to sign nums[i:] so that the whole expression ends at target
if i == n:
return 1 if total == target else 0
return count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
return count(0, 0)Memoize on position and running total
Intuition
count(i, total) depends only on i and total, not on the signs that produced the total. With nums = [1, 1, 1, 1], the prefixes +1 -1 and -1 +1 both reach total 0 at position 2, so the search from there is the same. Store each result the first time and reuse it.
The running total stays between -S and S, so shift it by S to use it as an index: memo[i][total + S]. There are at most n × (2S+1) states, about 4 × 10^4 for 20 numbers that sum to 1000, each with constant work.
Algorithm
- Compute
S = sum(nums)and make ann × (2S+1)memo filled with -1. - In
count(i, total), return the base case ati == nas before. - If
memo[i][total + S]is -1, fill it withcount(i+1, total + nums[i]) + count(i+1, total - nums[i]). - Return the stored value, and call
count(0, 0).
def findTargetSumWays(nums, target):
n = len(nums)
whole = sum(nums)
# memo[i][total + whole]: ways for nums[i:] from this running total, -1 while unknown
memo = [[-1] * (2 * whole + 1) for _ in range(n)]
def count(i, total):
if i == n:
return 1 if total == target else 0
if memo[i][total + whole] == -1:
memo[i][total + whole] = count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
return memo[i][total + whole]
return count(0, 0)Count the subsets that sum to (S + target) / 2
Intuition
Let P be the sum of the plus-signed numbers and N of the rest. Then P - N = target and P + N = S, so 2P = S + target. A sign choice works exactly when its plus group sums to (S + target) / 2, and each such subset is one sign choice.
ways[s] counts the subsets of the numbers seen so far that sum to s, starting from ways[0] = 1. For each number x, a subset reaching s either skips x or adds it to a subset reaching s - x. Go from the largest s down, so ways[s - x] still holds its value from before x and no number is used twice. A 0 adds every entry to itself, doubling all counts: the two signs of a zero. That is n × goal additions, at most 2 × 10^4.
Algorithm
- Compute
S = sum(nums). If|target| > SorS + targetis odd, return 0. - Set
goal = (S + target) / 2, makewaysofgoal + 1zeros and setways[0] = 1. - For each
xinnums, forsfromgoaldown tox, addways[s - x]toways[s]. - Return
ways[goal].
def findTargetSumWays(nums, target):
whole = sum(nums)
# plus - minus = target and plus + minus = whole, so plus = (whole + target) / 2
if abs(target) > whole or (whole + target) % 2 == 1:
return 0
goal = (whole + target) // 2
# ways[s]: how many subsets of the values seen so far add up to s
ways = [0] * (goal + 1)
ways[0] = 1
for x in nums:
# From the top down, so each value is used at most once
for s in range(goal, x - 1, -1):
ways[s] += ways[s - x]
return ways[goal]
Pitfalls and edge cases
- Skipping the parity check. For
[6, 3]and target 4,(9 + 4) / 2rounds down to 6, and the subset{6}gives 1 instead of 0. - Skipping the range check. For
[1, 2, 3]and target -10,(6 - 10) / 2 = -2, a negative array size. - Filling
waysfrom the bottom up. A number then joins a subset that already uses it:[1, 3]with target 2 reports 2 instead of 1. - Treating a zero as one choice.
[0, 0, 0, 1, 0, 0]with target -1 has 32 answers, one for every sign pattern of the five zeros. - Indexing a memo by a negative running total. Shift every total by
S, or use a hash map.
Frequently asked questions3
How is Target Sum related to the subset sum problem?
The numbers with a plus sign must sum to (S + target) / 2, so the answer is the number of subsets of nums with that sum. Any subset sum counting DP solves it once you add two checks: the value must be a whole number, and |target| must not exceed S.
What is the time complexity of Target Sum?
The subset counting DP runs in O(n × S) time with O(S) memory, where S is the sum of nums. The memoized recursion has the same time but an n × (2S+1) table. Trying every sign is O(2^n).
Can Target Sum be solved with a hash map of running totals?
Yes. Map each reachable running total to the number of sign prefixes that reach it, starting with {0: 1}, and build the next map from total + x and total - x for each number. The answer is the count at target. It is the memoized recursion run forward, in the same O(n × S) time.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def findTargetSumWays(nums, target):
# Write code hereTest #1
Test #2
Test #3
Arguments
nums = [2, 1, 1] target = 2
Expected Output
2