Description
Given an integer array nums and an integer target, return the number of different ways you can assign + or - to each number to reach the target sum.
Examples
Input:
nums = [1,1,1,1,1], target = 3Output:
5Explanation:
5 ways: -1+1+1+1+1, +1-1+1+1+1, +1+1-1+1+1, +1+1+1-1+1, +1+1+1+1-1.
Input:
nums = [2,3,1], target = 0Output:
2Explanation:
The two ways to reach target 0 are: +2-3+1 = 0 and -2+3-1 = 0.
Input:
nums = [100], target = -200Output:
0Explanation:
There is no way to assign + or - to the single number 100 to reach -200. It is possible to only get +100 or -100, neither of which equals -200.
Constraints
- •
1 ≤ nums.length ≤ 20 - •
0 ≤ nums[i] ≤ 1000 - •
-1000 ≤ target ≤ 1000