Signs That Hit a Target
Problem
Given a list of non-negative integers and a target, put a plus or a minus sign in front of every number and add them all up. Return how many different sign choices give exactly the target. A zero counts twice, since +0 and -0 are different choices.
Examples
Input: nums = [1, 2, 3, 4], target = 2
Output: 2
Why: -1 + 2 - 3 + 4 and 1 + 2 + 3 - 4 both give 2Input: nums = [0, 5], target = 5
Output: 2
Why: +0 + 5 and -0 + 5 are different choicesInput: nums = [3], target = 2
Output: 0
Why: edge case, only 3 and -3 are possibleHints
0 / 3
Split the numbers into the ones that get a plus and the ones that get a minus. What must the two group totals satisfy?
If P is the plus total and M the minus total, then P - M is the target and P + M is the sum of everything. So P is fixed, and the question becomes how many subsets add up to one particular value.
If the target is out of reach or has the wrong parity, the answer is 0. Otherwise let goal be half of the total plus the target and count subsets with that sum in a one-row table: one way to make 0 at the start, then for each number update the sums from goal down to that number, adding the ways to make the sum minus the number.
Solution
Choosing signs is the same as choosing the subset that gets a plus, and P - M = target together with P + M = total forces P = (total + target) / 2. Counting subsets with a fixed sum is 0/1 knapsack with counts in place of values, and walking the sums downward stops a number from being used twice in one pass. Zeros need no special case: each zero doubles every count, matching its two signs. Time is O(n × goal) and space is O(goal).
def sign_ways(nums, target):
total = sum(nums)
if abs(target) > total or (total + target) % 2:
return 0 # out of reach, or the wrong parity
goal = (total + target) // 2 # what the plus-signed numbers must add to
ways = [1] + [0] * goal
for x in nums:
for s in range(goal, x - 1, -1): # downward: each number used at most once
ways[s] += ways[s - x]
return ways[goal]
print(sign_ways([1, 2, 3, 4], 2)) # -> 2
print(sign_ways([0, 5], 5)) # -> 2
print(sign_ways([3], 2)) # -> 0Stuck on the idea rather than the code? 0/1 Knapsack covers it.