Target Sum Symbol Assignments
Given a list of non-negative integers nums and an integer target, assign either a + or - symbol to every element.
Return the number of different symbol assignments whose resulting expression equals target. Assignments are considered different when a different symbol is chosen for at least one index.
Method Signature
int findTargetSumWays(List<Integer> nums, int target)
nums contains the non-negative integers to which symbols must be assigned.target is the required value of the resulting expression.- Return the total number of valid symbol assignments.
Constraints
1 <= nums.size() <= 200 <= nums.get(i)- The sum of all values in
nums does not exceed 1,000.
- The returned answer fits within a signed 32-bit integer.
Examples
Example 1
findTargetSumWays(nums = [2, 1, 1], target = 2)
Output: 2
The valid expressions are +2+1-1 and +2-1+1.
Example 2
findTargetSumWays(nums = [1, 2, 4], target = 1)
Output: 1
The only valid expression is -1-2+4.
Example 3
findTargetSumWays(nums = [0, 0, 3], target = 3)
Output: 4
Each zero may independently receive either symbol, producing four distinct assignments while the resulting sum remains 3.