SEA403 恰好装满的工具箱

难度梯度：T3｜训练重点：DFS 子集、界限剪枝

题目描述

有 N 件重量各不相同的工具，第 i 件重 a_i。每件至多选择一次，求总重量恰好为 T 的选择方案数量。方案只由所选工具编号决定，不考虑选择顺序。

选择工具时只考虑工具编号的集合，不考虑取出的先后顺序；每件工具至多一次。没有可行集合时输出 0。

输入格式

第一行 N T；第二行 N 个正整数 a_i。

输出格式

输出方案数量。

样例输入

4 5
1 2 3 4

样例输出

2

样例说明

可选编号 {1,4} 或 {2,3}。

数据范围

1≤N≤22；1≤T≤10^9；1≤a_i≤10^9；答案保证不超过 2^22。

子任务

20 分：N≤15；30 分：所有 a_i>T/2；50 分：无附加限制。