278. digital combination

Given N A positive integer A1,A2,…,ANA1,A2,…,AN, Choose a number from them , Make their sum for M, Find out how many options there are .

Input format

The first line contains two integers N and M.

The second line contains N It's an integer , Express A1,A2,…,AN.

Output format

Contains an integer , Indicates the number of options .

Data range

1≤N≤100,
1≤M≤10000,
1≤Ai≤1000,
The answer is guaranteed in int Within the scope of .

sample input ：

4 4

1 1 2 2

sample output ：

3

This problem is actually to use the total number of schemes = choice a[i] Number of alternatives + No choice a[i] The total number of schemes added up

#include<iostream>
using namespace std;
int main()
{
	int n,m;
	int a[110],f[10010];//f[i] Express and for i Number of alternatives  
	cin>>n>>m;
	f[0]=1;// And for 0 It's like choosing none , There is only one case 
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		for(int j=m;j>=a[i];j--)
			f[j]+=f[j-a[i]];// And for j The total number of programs = Choose the first i The number of schemes + No second choice i The number of schemes  
	}
	cout<<f[m]<<endl;
	return 0;
}