[text] priyanshu

Viewer

copydownloadembedprintName: priyanshu
  1. //User function template for C++
  2. bool solve(vector<int>&arr,int sum,vector<int>&dp,int n){
  3.     
  4.     if(dp[sum]==1){
  5.         return true;
  6.     }
  7.     
  8.     if(dp[sum]=-1){
  9.         return false;
  10.     }
  11.     
  12.     if(sum==0){
  13.         dp[sum]=1;
  14.         return true;
  15.     }
  16.     else if(n==0){
  17.         return false;
  18.     }
  19.     else if(sum<0){
  20.         dp[sum]=-1;
  21.         return false;
  22.     }
  23.     
  24.     bool take= solve(arr,sum-arr[n],dp,n-1);
  25.     bool not_take=solve(arr,sum,dp,n-1);
  26.     if(take==true||not_take==true){
  27.         dp[sum]=1;
  28.         return true;
  29.     }
  30.     
  31.     dp[sum]=-1;
  32.     return false;
  33.     
  34. }
  35.  
  36. class Solution{   
  37. public:
  38.     bool isSubsetSum(vector<int>arr, int sum){
  39.         vector<int>dp(sum+1,-2);
  40.         
  41.         int n=arr.size()-1;
  42.     
  43.     return solve(arr,sum,dp,n);
  44.     }
  45. };
  46.  
  47. //{ Driver Code Starts.
  48. int main() 
  49. { 
  50.     int t;
  51.     cin>>t;
  52.     while(t--)
  53.     {
  54.         int N, sum;
  55.         cin >> N;
  56.         vector<int> arr(N);
  57.         for(int i = 0; i < N; i++){
  58.             cin >> arr[i];
  59.         }
  60.         cin >> sum;
  61.         
  62.         Solution ob;
  63.         cout << ob.isSubsetSum(arr, sum) << endl;
  64.     }
  65.     return 0; 
  66. } 
  67.  
  68. // } Driver Code Ends

Editor

You can edit this paste and save as new:


File Description
  • priyanshu
  • Paste Code
  • 16 May-2024
  • 1.2 Kb
You can Share it: