The problem
Put a + or a − in front of each number in nums, and add them up. Return the number of ways to choose the signs so the total is target.
Examples
01
- Input
nums = [1, 1, 1, 1, 1], target = 3
- Output
5
02
- Input
nums = [1], target = 1
- Output
1
Constraints
- 1 ≤ nums.length ≤ 20
- 0 ≤ nums[i] ≤ 1000
- The numbers sum to at most 1000.
- −1000 ≤ target ≤ 1000
The idea
Call the numbers given + the group P and those given − the group N. Then P − N = target and P + N = total. Adding the two: P = (total + target) ÷ 2. So the question is just how many subsets add up to that — and if total + target is odd, or target is out of reach, the answer is 0.
Count subsets with sum s as in Partition Equal Subset Sum, but counting instead of yes/no: each number x adds ways[s − x] to ways[s], going downwards so x is used once. A 0 doubles every count, since +0 and −0 are both fine.
- Time
- O(n × total)
- Space
- O(total)
Solution · every language run against every case
class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: # Split the numbers into those given + (summing to P) and those given - (summing to N): # P - N = target and P + N = total, so P = (total + target) / 2. Count subsets summing to P. total = sum(nums) if abs(target) > total or (total + target) % 2: return 0 goal = (total + target) // 2 ways = [1] + [0] * goal # ways[s]: subsets of the numbers so far that sum to s for x in nums: for s in range(goal, x - 1, -1): # downwards, so x is used at most once ways[s] += ways[s - x] return ways[goal]