recursion prpblem 1 sde sheet (Subset sum)

 class Solution {

  public:

  

    bool Sum(int rsum,vector<int>&arr,int idx,vector<vector<int>>&dp){

        if(rsum==0)return true;

        if(rsum<0)return false;

        if(idx==0)return(arr[idx]==rsum);

        if(dp[idx][rsum]!=-1)return dp[idx][rsum];

        

        

        bool ans1=Sum(rsum-arr[idx],arr,idx-1,dp);

        if(ans1)return dp[idx][rsum]=ans1;

        bool ans2=Sum(rsum,arr,idx-1,dp);

        return dp[idx][rsum]=ans2;

    }

    bool isSubsetSum(vector<int>& arr, int sum) {

        // code here

        int n=arr.size();

        vector<vector<bool>>dp(n,vector<bool>(sum+1,false));

        //return Sum(sum,arr,arr.size()-1,dp);

        for(int i=0;i<n;i++)dp[i][0]=true;

        if(arr[0]<sum)dp[0][arr[0]]=true;

        for(int i=1;i<n;i++){

            for(int j=1;j<=sum;j++){

                if(j<arr[i])dp[i][j]=dp[i-1][j];

                else dp[i][j]=dp[i-1][j-arr[i]]||dp[i-1][j];

            }

        }

        return dp[n-1][sum];

    }

};