给定N个正整数A1,A2,…,AN,从中选出若干个数,使它们的和为M,求有多少种选择方案。
输入格式
第一行包含两个整数N和M。
第二行包含N个整数,表示A1,A2,…,AN。
输出格式
包含一个整数,表示可选方案数。
数据范围
1≤N≤100,
1≤M≤10000,
1≤Ai≤1000
输入样例:
4 4
1 1 2 2
输出样例:
3
/*
01背包问题
状态表示:f[i][j]表示从前i个物品中选数的和为j的方案的数目;
属性:数目;
状态计算:f[i][j]=f[i-1][j]+f[i-1][j-A[i]];
选这个和不选这个的和
初始化:f[0][0]为1,从前0个中选数为0的数为1;
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=520;
ll f[N];
int main()
{
ll n,m;
cin>>n>>m;
f[0]=1; //F[0][0]为1,从前0个中选数为0的数为1;
while(n--)
{
ll a;
cin>>a;
for(ll i=m;i>=a;i--)f[i]=f[i]+f[i-a];
}
cout<<f[m]<<endl;
}