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 concatenate all the integers.

Return the number of different expressions that you can build, which evaluates to target.

Examples

Example 1:

Input: nums = [1,1,1,1,1], target = 3

Output: 5

Explanation: There are 5 ways to assign symbols to make the sum equal 3:

-1 + 1 + 1 + 1 + 1 = 3

+1 - 1 + 1 + 1 + 1 = 3

+1 + 1 - 1 + 1 + 1 = 3

+1 + 1 + 1 - 1 + 1 = 3

+1 + 1 + 1 + 1 - 1 = 3

Example 2:

Input: nums = [1], target = 1

Output: 1

Explanation: The only way is +1 = 1.

Example 3:

Input: nums = [1,0], target = 1

Output: 2

Explanation: The two ways are +1 + 0 = 1 and +1 - 0 = 1.

Constraints

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000