242011 - T2-选数求和

题目描述

给定 n 个正整数:

a_1,a_2,\ldots,a_n

现在可以从这 n 个数中选择任意多个数,也可以一个都不选。

每个数最多选择一次。

请计算有多少种不同的选择方案,使得所选数字之和恰好等于 S。

注意:

  • 不同位置的数字视为不同元素。
  • 即使两个位置的数字相同,选择方案也可能不同。
  • 只统计选择方案数量。
输入

第一行输入两个正整数 n、S。

第二行输入 n 个正整数a_1,a_2,\ldots,a_n。

输出

输出一个整数,表示满足条件的选择方案数量。

样例

输入

4 5
1 2 3 4

输出

2
说明

样例解释

共有两种合法方案:

  1. 选择 1 和 4,和为 5。
  2. 选择 2 和 3,和为 5。

因此答案为 2。

数据范围

  • 1 ≤ n ≤ 20
  • 1 ≤ a_i ≤ 100
  • 1 ≤ S ≤ 2000
标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 基础


上一题 下一题