Description
Assign either a plus or minus sign to each nonnegative input value. Count assignments whose total equals target. Equal values and zero occurrences are separate choices.
Solution
def find_target_sum_ways(nums, target):
counts = {0: 1}
for value in nums:
following = {}
for total, ways in counts.items():
following[total + value] = following.get(total + value, 0) + ways
following[total - value] = following.get(total - value, 0) + ways
counts = following
return counts.get(target, 0)Examples
Example 1
- Input
[[1,1,1,1,1],3]- Output
5
Choose which one of five 1s receives the minus sign.
Example 2
- Input
[[0,0,1],1]- Output
4
Each zero has two sign choices.
Example 3
- Input
[[1],2]- Output
0
Neither sign yields 2.
Approach
Maintain a map from achievable sums to assignment counts. For each number, build a new map adding both plus and minus outcomes from every previous sum. Zero adds both choices to the same sum.
Time & space
O(n S) time and O(S) auxiliary space, where n is element count and S = 2 sum(nums) + 1 bounds possible sums.