凑出目标的物品选法

难度：T2

【知识点：递归枚举、搜索剪枝】

前置知识：数组、函数、递归状态、可行性与顺序规则。

题目描述

有 $n$ 件物品，编号为 $1$ 到 $n$，第 $i$ 件重量为正整数 $a_i$。每件至多选择一次，求总重量恰好为 $S$ 的选法数。选取顺序不构成新选法；不同编号即使重量相同仍是不同物品。全部不选也算一种选法，其重量为 $0$。

输入格式

第一行两个整数 $n,S$。第二行 $n$ 个整数 $a_1,\ldots,a_n$。

输出格式

一行一个整数，表示总重量恰好为 $S$ 的选法数；没有则输出 $0$。

样例输入

3 6
2 4 5

样例输出

1

样例解释

只选第 $1,2$ 件，重量为 $2+4=6$。

数据范围

$1\le n\le20$，$0\le S\le20000$，$1\le a_i\le1000$。