surajmateti

Gfg one

Oct 21st, 2021
744
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Initial template for C++
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6.  // } Driver Code Ends
  7. //User function template for C++
  8.  
  9. class Solution{  
  10.     int fun(int i ,int csum , int n , int a[], vector<vector<int>>&dp)
  11.     {
  12.         if(i == n-1)
  13.         {
  14.             if(a[i] == csum) return 1; return 0;
  15.         }
  16.         if(csum < 0) return 0;
  17.        
  18.         if(csum == 0) return 1;
  19.        
  20.         if(dp[i][csum]!=-1) return dp[i][csum];
  21.        
  22.         // if(a[i] > csum)
  23.        
  24.         // return dp[i][csum] = fun(i+1,csum,n,a,dp);
  25.        
  26.         //else
  27.        
  28.         return dp[i][csum] = max(fun(i+1,csum-a[i],n,a,dp) , fun(i+1,csum,n,a,dp) );
  29.     }
  30. public:
  31.     bool isSubsetSum(int n, int a[], int sum){
  32.         // code here
  33.         //memset(dp,0,sizeof dp);
  34.         vector<vector<int>>dp(n,vector<int>(sum+1,-1));
  35.         return fun(0,sum,n,a,dp);
  36.        
  37.        
  38.     }
  39. };
  40.  
  41. // { Driver Code Starts.
  42. int main()
  43. {
  44.     int t;
  45.     cin>>t;
  46.     while(t--)
  47.     {
  48.         int N, sum;
  49.         cin >> N;
  50.         int arr[N];
  51.         for(int i = 0; i < N; i++){
  52.             cin >> arr[i];
  53.         }
  54.         cin >> sum;
  55.        
  56.         Solution ob;
  57.         cout << ob.isSubsetSum(N, arr, sum) << endl;
  58.     }
  59.     return 0;
  60. }
  61.   // } Driver Code Ends
RAW Paste Data