链接: https://cses.fi/problemset/task/1628

板块: Advanced Techniques

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个包含 $n$ 个数的数组。有多少种方式可以选出一个子集，使其元素之和等于 $x$？

输入

第一行有两个数 $n$ 和 $x$：数组大小与目标总和。

第二行有 $n$ 个整数 $t_1,t_2,\dots,t_n$：数组中的各个数。

输出

输出能使总和等于 $x$ 的方案数。

数据范围

$1 \le n \le 40$ $1 \le x \le 10^9$ $1 \le t_i \le 10^9$

样例输入

4 5
1 2 3 2

样例输出

3