A puzzle shows the numbers nums in a row. You must write a + or a - in front of every number and then evaluate the expression. Return the number of sign assignments whose value equals target.
Examples
Input: nums = [1, 1, 2], target = 2
Output: 2
Explanation: +1 -1 +2 and -1 +1 +2.
Input: nums = [2, 2], target = 0
Output: 2
Constraints
1 <= len(nums) <= 600 <= nums[i] <= 100,-6000 <= target <= 6000- Target complexity: O(n * sum(nums)) time; enumerating 2^n assignments is infeasible.
Goals
- Count sign assignments by tracking a distribution of running totals
- Use a dictionary or offset array to handle negative sums