Subset Sum

#include <iostream>

#include <cstdio>

using namespace std;

#define siz 1000005

#define INF 999999999

int a[siz],b[siz];



int main()

{

    int N,sum,n;

    //freopen("input.txt","r",stdin);

    scanf("%d",&n);

    for(int t=0;t<n;t++){

        scanf("%d%d",&N,&sum);



        for(int i=0;i<N;i++) scanf("%d",&b[i]);



        for(int i=1;i<=sum;i++) a[i]=INF;

            a[0]=0;

            for(int i=0;i<N;i++){

                for(int j=sum;j>=0;j--){

                    if(a[j]!=INF){

                        if(b[i]+j<=sum){

                            a[b[i]+j]=1;

                        }

                    }

                }

            }

        if(a[sum]==1) puts("1");

        else puts("0");

    }

    return 0;

}