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.
For example, if `nums = [2, 1]`, you can add a `'+'` before `2` and a `'-'` before `1` and concatenate them to build the expression `"+2-1"`.
Return the number of different expressions that you can build, which evaluates to `target`.
### Constraints
- `1 <= nums.length <= 20`
- `0 <= nums[i] <= 1000`
- `0 <= sum(nums[i]) <= 1000`
- `-1000 <= target <= 1000`
### Input Format
- Line 1: An integer `target`.
- Line 2: Space-separated integers representing `nums`.
### Output Format
Print the number of different expressions that evaluate to target.
Sample Cases
Example 1Sample Case
Input: 3
1 1 1 1 1
Output: 5
Example 2Sample Case
Input: 1
1
Output: 1
Example 3Sample Case
Input: 3
1
Output: 0
Example 4Sample Case
Input: 3
3
Output: 1
Constraints
Runtime Limit: 2000 ms per test batch
Memory Limit: 256 MB
Standard I/O stream reading
Official submissions are evaluated against hidden test cases on the server to verify time & memory complexity.