#include<bits/stdc++.h>
#define MX 1000007
#define ll long long
#define ull unsigned long long
using namespace std;
int main()
{
int n,sum;
cin>>n>>sum;
int Set[n+1];
bool mat[n+1][sum+1];
for(int i=1;i<=n;i++)
cin>>Set[i];
for(int i=0;i<=n;i++)
mat[i][0]=true; // when j=0, 1st column value should 1 (0 to n)
for(int i=1;i<=sum;i++)
mat[0][i]=false; // 1st row should 0 (row no. 1 to sum)
for(int i=1;i<=n;i++){
for(int j=1;j<=sum;j++){
if(j<Set[i]) // when coin is greater than sum
mat[i][j]=mat[i-1][j];
else
mat[i][j]=mat[i-1][j] || mat[i-1][j-Set[i]];
}
}
cout<<mat[n][sum]<<endl;
return 0;
}
No comments