surajmateti

Leetcode one

Oct 21st, 2021
737
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.     int dp[21][1001];
  3.     int fun(int i,int n,int target,vector<int>&a)
  4.     {  
  5.         //if(csum == target) return 1;
  6.         if(target == 0)
  7.         {
  8.             return 1;
  9.         }
  10.         if(target < 0) return 0;
  11.         if(i == n-1)
  12.         {
  13.            if(target - a[i] == 0) return 1; return 0;
  14.         }
  15.        
  16.         if(dp[i][target]!=-1) return dp[i][target];
  17.         int op1  = a[i] > 0? fun(i+1,n,target-a[i],a):0;
  18.         int op2  = fun(i+1,n,target,a);
  19.         return dp[i][target] = op1 + op2;
  20.     }
  21. public:
  22.     int findTargetSumWays(vector<int>& a, int target) {
  23.         int n = a.size();
  24.         memset(dp,-1,sizeof dp);
  25.         int sum =  0 , c = 0;
  26.         for(int x:a) {sum += x; if(x == 0) c++;}
  27.         if( (target + sum) & 1) return 0;
  28.         if(target > sum) return 0;
  29.         return fun(0,n,(target+sum)>>1,a) * (1<<c);
  30.     }
  31. };
RAW Paste Data