每件一次的恰好选法

难度：T2

【知识点：搜索记忆化与DP】

前置知识：完整状态、基础值、0/1与完全背包计数。

题目描述

有n件带编号物品，重量为w[i]，每件最多选一次。求选出重量恰好W的不同物品子集数量。不同编号即不同物品，即使重量相同也不能合并。W=0时空子集算一种。

输入格式

第一行n W，第二行n个重量；n=0时可省略第二行。

输出格式

一行方案数，不取模。

样例输入

2 1
1 1

样例输出

2

样例解释

可以选编号1或编号2，共2种，虽然重量相同。

数据范围

0≤n≤25，0≤W≤100，1≤w[i]≤100。