Gfg one

//Initial template for C++

#include<bits/stdc++.h>
using namespace std;

 // } Driver Code Ends
//User function template for C++

class Solution{
    int fun(int i ,int csum , int n , int a[], vector<vector<int>>&dp)
    {
        if(i == n-1)
        {
            if(a[i] == csum) return 1; return 0;
        }
        if(csum < 0) return 0;

        if(csum == 0) return 1;

        if(dp[i][csum]!=-1) return dp[i][csum];

        // if(a[i] > csum)

        // return dp[i][csum] = fun(i+1,csum,n,a,dp);

        //else

        return dp[i][csum] = max(fun(i+1,csum-a[i],n,a,dp) , fun(i+1,csum,n,a,dp) );
    }
public:
    bool isSubsetSum(int n, int a[], int sum){
        // code here
        //memset(dp,0,sizeof dp);
        vector<vector<int>>dp(n,vector<int>(sum+1,-1));
        return fun(0,sum,n,a,dp);


    }
};

// { Driver Code Starts.
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int N, sum;
        cin >> N;
        int arr[N];
        for(int i = 0; i < N; i++){
            cin >> arr[i];
        }
        cin >> sum;

        Solution ob;
        cout << ob.isSubsetSum(N, arr, sum) << endl;
    }
    return 0;
}
  // } Driver Code Ends