Partition Equal Subsets Sum- DP on Subsequence

Problem Link:

https://www.codingninjas.com/studio/problems/partition-equal-subset-sum-_892980?utm_source=striver&utm_medium=website&utm_campaign=a_zcoursetuf

My Approach:

We will use the concept of 'Take' and 'Not Take' cases.

Observation:

S1 = S2 = TotalSum/2;

So we just need to check for subset sum for k (where k is Total Sum / 2).

Code:

// TIME COMPLEXITY : O(N^2)
// SPACE COMPLEXITY : O(N*K) + Auxiliary Stack Space , K is TotalSum/2

bool helper(vector<int> &arr, int i, int target, vector<vector<int>> &dp){

    if(target==0){
        return true;
    }
    if(i==0){
        if(arr[i]==target){
            return true;
        }else{
            return false;
        }
    }

    if(dp[i][target]!=-1){
        return dp[i][target];
    }

    int notPick = helper(arr,i-1,target,dp);
    int pick = false;
    if(arr[i]<=target){
        pick = helper(arr,i-1,target-arr[i],dp);
    }

    dp[i][target] = pick || notPick;
    return pick || notPick;
}

bool canPartition(vector<int> &arr, int n)
{
    // Write your code here.
    int sum = 0;

    for(int i=0;i<n;i++){
        sum+=arr[i];
    }

    if(sum%2==1){
        return false;
    }

    vector<vector<int>> dp(n, vector<int>(sum/2+1,-1));

    return helper(arr,n-1,sum/2,dp);
}