普及-⏱ 1000ms💾 256MB#P3174🏷️ 动态规划计数

题目描述

收藏社有 $n$ 枚纪念币,每枚面额为正整数,每枚至多选用一次。 社长想挑出其中若干枚,使面额总和恰好为 $t$。

求有多少种不同的挑选方案(只看选用了哪些枚,与挑选顺序无关)。

输入格式

第一行两个正整数 $n$ 和 $t$,用空格隔开; 第二行 $n$ 个正整数,为各枚纪念币的面额,用空格隔开。

输出格式

一行,一个整数:面额总和恰为 $t$ 的挑选方案数。

数据范围

$$1 \le n \le 20,\quad 1 \le t \le 1000$$
,面额为不超过 $1000$ 的正整数。

样例输入 #1
5 5
1 2 3 4 5
样例输出 #1
3
样例输入 #2
1 1
1
样例输出 #2
1