You get an array of integers nums and a number target.
Put either + or - in front of every number in nums, then add everything up. For example, with nums = [2, 1] you can write +2-1, which is 1.
Return how many different ways of choosing the signs give a total exactly equal to target. Two ways are different if at least one number gets a different sign.
Examples
Example 1:
Input: nums = [1,2,1], target = 2
Output: 2
Explanation: +1+2-1 and -1+2+1 both equal 2. That is 2 ways.
Example 2:
Input: nums = [2,2,2], target = 2
Output: 3
Explanation: Exactly one number gets "-" in each way: +2+2-2, +2-2+2 and -2+2+2. That is 3 ways.
Example 3:
Input: nums = [5], target = 3
Output: 0
Explanation: The total can only be 5 or -5, so there is no way.