Target Sum

You are given an integer array nums and an integer target.

You want to build an expression out of the numbers in nums by adding either a + or - sign before each integer. Return the number of different expressions that evaluate to target.

---

Example 1

Input: nums = [1, 1, 1, 1, 1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols:
-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: +1 = 1 is the only expression that evaluates to 1.

---

Constraints

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