Untitled

//User function template for C++
bool solve(vector<int>&arr,int sum,vector<int>&dp,int n){
    
    if(dp[sum]==1){
        return true;
    }
    
    if(dp[sum]=-1){
        return false;
    }
    
    if(sum==0){
        dp[sum]=1;
        return true;
    }
    else if(n==0){
        return false;
    }
    else if(sum<0){
        dp[sum]=-1;
        return false;
    }
    
    bool take= solve(arr,sum-arr[n],dp,n-1);
    bool not_take=solve(arr,sum,dp,n-1);
    if(take==true||not_take==true){
        dp[sum]=1;
        return true;
    }
    
    dp[sum]=-1;
    return false;
    
}

class Solution{   
public:
    bool isSubsetSum(vector<int>arr, int sum){
        vector<int>dp(sum+1,-2);
        
        int n=arr.size()-1;
    
    return solve(arr,sum,dp,n);
    }
};


// yaha tak hi tha mera code




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

// } Driver Code Ends