Ways to reach a target with plus and minus
Turn a plus/minus assignment problem into a subset-sum counting problem with some algebra first. About 14 minutes.
Plus or minus in front of every number
Put a plus or a minus sign in front of each number, then add them all up. How many sign choices land exactly on the target?
Here's the key shift. The plus-numbers form one group and the minus-numbers the other. Their difference is the target, and together they add up to the total. A little algebra says the plus group must add up to exactly half of (total + target). So you're really counting groups of numbers that reach one particular sum.
Count, don't just tick
Use the checklist from before, but write counts instead of ticks: how many different groups reach each total. When a new number arrives, every way of making the old total is also a way of making the bigger one.
For five 1s and target 3, the plus group must reach (5 + 3) ÷ 2 = 4. There are 5 ways to pick four of the five 1s, so 5 ways to place the signs.
total = sum(nums)
if abs(target) > total:
return 0
if (total + target) % 2 == 1:
return 0
want = (total + target) // 2
count = [1] + [0] * want
for x in nums:
for s in range(want, x - 1, -1):
count[s] += count[s - x]
return count[want]The plus-numbers must add up to (total + target) ÷ 2 = 4. So count subsets with sum 4. Before any item: one way to make 0.
nums = [1, 1], target = 0. How many ways are there?
- A2
- B1
Show the answer
2. +1 -1 and -1 +1 both give 0: two different sign assignments, even though the numbers are equal.
Ways to reach a target with plus and minus
Given an array nums of non-negative integers, you assign a + or a - sign to each number and add them all up. Return how many different ways of assigning signs make the total equal target.
nums = [1, 1, 1, 1, 1], target = 3 → 5
1 ≤ nums.length ≤ 200 · 0 ≤ nums[i] ≤ 100 · -20,000 ≤ target ≤ 20,000