1053. 子集和问题

单点时限: 2.0 sec

内存限制: 256 MB

对于集合 $S={s_1,s_2,\ldots,s_n}$,求子集数量,要求该子集的元素之和 $d=X$。

输入格式

第一行有一个整数 $T$,表示有 $T$ 组测试数据 .

每组测试数据的第一行为整数 $n$ 和 $X$。$n$ $(1 \leq n \leq 100)$ 表示集合 $S$ 有 $n$ 个不同的元素,$X$ 表示所求的元素之和为 $X$ $(1 \leq X \leq 10~000)$.

接下去的 $n$ 行,每行含一个整数 $s_i$ $(1 \leq s_i \leq 1~000)$。

输出格式

每组测试数据输出一行,每行只有一个整数,表示有多少个不同的子集,使得子集的元素之和为 $X$。

样例

Input
1
4 9
1
2
6
8
Output
2

提示

此题数据已加强。

24 人解决,341 人已尝试。

44 份提交通过,共有 1036 份提交。

7.8 EMB 奖励。

创建: 18 年,5 月前.

修改: 7 年,1 月前.

最后提交: 1 年,2 月前.

来源: N/A

题目标签
DP