Target Sum
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenating all the integers.
- For example, if
nums = [2, 1], you can add a'+'before2and a'-'before1and concatenate them to build the expression"+2-1".
Return the number of different expressions that you can build which evaluate to target.
Example 1
Input
nums = [1,1,1,1,1], target = 3Output
5There are 5 ways to assign symbols to make the sum of nums be target 3.
Example 2
Input
nums = [1], target = 1Output
1The only expression is +1, which evaluates to the target 1.
Constraints
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 1000