‹ 上一题下一题 ›

j01408. 子集和恰好计数未做

1000 ms 256 MB 测试点 10 通过率 100% 6级·深度优先搜索深度优先搜索阶梯·进阶暴力枚举子集型枚举

文件读写输入j01408.in输出j01408.out

题目描述

小 G 拿到 $n$ 个数，想从中挑出若干个数组成一个子集，使子集里所有元素的和恰好等于 $t a r g e t$ 。请你帮他算一算，满足要求的选法一共有多少种。

输入格式

第一行两个整数 $n, t a r g e t$ ；接下来 $n$ 行每行一个整数 $a_{i}$ 。

输出格式

一行一个整数，方案数。

样例

输入

输出

数据范围

$1 \leq n \leq 20$
$1 \leq t a r g e t \leq 1000$
$1 \leq a_{i} \leq 50$

输入

输出

答案