7815: [CSES Problem Set] Meet in the Middle
[Creator : ]
Description
You are given an array of $n$ numbers. In how many ways can you choose a subset of the numbers with sum $x$?
Input
The first input line has two numbers $n$ and $x$: the array size and the required sum.
The second line has $n$ integers $t_1,t_2,…,t_n$: the numbers in the array.
The second line has $n$ integers $t_1,t_2,…,t_n$: the numbers in the array.
Output
Print the number of ways you can create the sum $x$.
Constraints
$1≤n≤40$
$1≤x≤10^9$
$1≤t_i≤10^9$
$1≤x≤10^9$
$1≤t_i≤10^9$
Sample 1 Input
4 5
1 2 3 2
Sample 1 Output
3