Posted on

Subset Sum Problem from Geeks for Geeks


class Solution {
  public:
    bool isSubsetSum(vector<int>& arr, int sum) {
        
        vector<vector<int>> memo(arr.size()+1, vector<int>(sum+1, -1));
        
        
        function<bool(vector<int>&, int, int)> dp = [&](vector<int>& ar, int index, int sum){
            
            
            if( sum == 0 ) return true;
            if( index == 0 ) return false;
            
            if( memo[index][sum] != -1 )
                return memo[index][sum]==1;
            
            bool result = dp(ar, index-1, sum );
            
            
            if( ar[index-1] <= sum  )
                result = result || dp(ar, index-1, sum - ar[index-1]);
            
            memo[index][sum] = result;
            return result ;
        };
        
        return dp(arr, arr.size(), sum);
        
        
    }
};