Question
Mystic Math
In a magical kingdom, Aria possesses a unique array of numbers called "vals." Her quest is to form an expression that equals a given target value. She can concatenate the numbers in any order, inserting either a "+" or "-" before each number to build the expression. Determine how many distinct expressions she can create that evaluate to the target value.
Input
The first line of the input contains the integer N, denoting the number of elements in the array.
The second line of the input contains N space-separated integers, denoting the elements of the array vals.
The third line of the input contains a single integer T, denoting the target integer.
Constraints
1 ≤ N ≤ 20
0 ≤ vals[i] ≤ 1000
0 ≤ sum(vals[i]) ≤ 1000
-1000 ≤ T ≤ 1000
The second line of the input contains N space-separated integers, denoting the elements of the array vals.
The third line of the input contains a single integer T, denoting the target integer.
Constraints
1 ≤ N ≤ 20
0 ≤ vals[i] ≤ 1000
0 ≤ sum(vals[i]) ≤ 1000
-1000 ≤ T ≤ 1000
Output
Return the number of different expressions that you can build, which evaluates to the target.
Example
Sample Input
5
1 1 1 1 1
3
Sample Output
5
Explanation
There are 5 ways to assign symbols to make the sum of nums be target 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
5
1 1 1 1 1
3
Sample Output
5
Explanation
There are 5 ways to assign symbols to make the sum of nums be target 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