Meet in the Middle.

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, ~~Swift~~, TCL, Text, Turing, VB, Zig

Se te da un arreglo de $n$ ~n~ números. ¿De cuántas maneras puedes elegir un subconjunto de los números cuya suma sea $x$ ~x~?

Entrada

La primera línea de entrada contiene dos números, $n$ ~n~ y $x$ ~x~: el tamaño del arreglo y la suma requerida.
La segunda línea contiene $n$ ~n~ enteros $t_1,t_2,\dots,t_n$ ~t_1,t_2,\dots,t_n~: los números del arreglo.

Salida

Imprime el número de maneras en que puedes crear la suma $x$ ~x~.

Restricciones

$1 \leq n \leq 40$ ~1 \leq n \leq 40~
$1 \leq x \leq 10^9$ ~1 \leq x \leq 10^9~
$1 \leq t_i \leq 10^9$ ~1 \leq t_i \leq 10^9~

Ejemplo de Entrada

4 5
1 2 3 2

Ejemplo de Salida

Comments

There are no comments at the moment.