Target Sum
Implement targetSum
Given an array of non-negative integers and a target value, count how many different ways a plus or minus sign can be placed in front of every number so that the resulting expression evaluates to exactly the target. Every number must receive exactly one sign, and every distinct choice of signs counts as a separate way, even if two choices happen to use the same signs on equal-valued numbers at different positions.
Splitting the numbers by the sign they end up with turns this into a partition question: the numbers assigned a plus sign form one group, the numbers assigned a minus sign form the other, and the group sums are related to the target and the array's total in a fixed way — knowing any two of "positive group sum," "negative group sum," and "target" pins down the third. That reduces the problem to counting how many subsets of the array sum to one specific, precomputed amount — the same counting search used for Count Subsets with Sum K, just with that amount derived from the total and the target first.
Example 1:
Input: nums = [2,3,4,1], target = 2
Output: 2
Example 2:
Input: nums = [5,3,2], target = 0
Output: 2
Example 3:
Input: nums = [1,2,1], target = 4
Output: 1
+ 7 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ nums.length ≤ 20 - ●
0 ≤ nums[i] ≤ 100 - ●
0 ≤ target ≤ 1000
nums =
[2, 3, 4, 1]
target =
2