DAY 16 - Partition Equal Subset Sum

Hello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day-16.

DAY 16 Problem: Partition Equal Subset Sum

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Intuition:
This problem is very similar to the last question we wrote here.
There is not much change here and we will proceed with the same approach almost. For someone reading this the first time, I will try to explain it again.

*Observation: *
If you look closely the question asks us to divide the sum into two equal subsequences. That would never be possible if the sum of total array is an odd number. Hence we will proceed with that first. If it's even we need to find a subsequence with total sum of sum/2 and other condition will automatically become true.
Now this question is just the old question with target as sum/2;

Approach: Recursion

• Apply the observation into an if case.
• Base Case establishment: Start from the last index.
• If we have reached our required sum/target, we return true.
• If we have reached the end of our iteration in a recursive way, just see if the last index leads to our target.
• Now that we have established base cases, let's form the recursive relation.(Observe what's changing and what we need at every step).
• We need an index, our target and the array of values.
• Two Options: Take the element in subset or not.
• Not Taken: We just decrement the index.
• Taken: First we need to see if target >= arr[index]. Then if it is: We decrement the index and update target.
• return taken || notTaken.

Code:

bool partitionHelper(int index, int target, vector<int>& nums)


    {
        if(target == 0){
            return true; //base case for satsifactory result
        }
        if(index == 0)
        return nums[0] == target;

        //two choices
        //not taken
        bool notTaken = partitionHelper(index-1, target, nums);
        bool taken = false;

        if(target >= nums[index]){
            taken = partitionHelper(index-1,target-nums[index], nums);
        }
    return notTaken || taken;
    }
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for(int i = 0; i < n; i++)
        {
            sum = sum + nums[i];
        }
        if(sum%2 == 1){
            return false;
        }
        else{
            return partitionHelper(n-1,sum/2,nums);
        }

    }

This will TLE in extreme test cases. We will reduce it's time complexity with Memoization.

Approach: Recursion + Memoization

• Initialize a DP vector of vector of type int of the size of index and target with value -1.
• That's because at max we will have to go for index values and target times.
• Whenever we want to find the answer of particular parameters (say subsetHelperMemo(ind,target)), we first check whether the answer is already calculated using the dp array(i.e dp[ind][target]!= -1 ). If yes, simply return the value from the dp array.
• We set every value that we return as it's dp[index][target] as return to store it.

Code:

bool Memo(int index, int target, vector<int>& nums, vector<vector<int>>& dp)
    {
        if(target == 0){
            return true; //base case for satsifactory result
        }
        if(index == 0)
        return nums[0] == target;
        if(dp[index][target]  != -1){
            return dp[index][target];
        }
        //two choices
        //not taken
        bool notTaken = Memo(index-1, target, nums,dp);
        bool taken = false;

        if(target >= nums[index]){
            taken = Memo(index-1,target-nums[index], nums,dp);
        }
    return dp[index][target] = notTaken || taken;
    }
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for(int i = 0; i < n; i++)
        {
            sum = sum + nums[i];
        }
        if(sum%2 == 1){
            return false;
        }
        else{
            vector<vector<int>> dp(n, vector<int>((sum/2) + 1,-1)); 
            return Memo(n-1,sum/2,nums,dp);
        }

    }

Complexity Analysis:

Time Complexity: O(N*K) + O(N)
Space Complexity: O(N) + O(N*K). Recursion Stack Space.

We will use tabulation to reduce recursion stack space.

To convert a recursive solution into tabulation one, Our approach doesn't change , we simply change the way we store dp values.

• Initialize a Boolean vector> dp of same size as done before and initialize as false.
• If our target is matched/reduced to 0. It can take any values from the any of starting index. Hence we initialize all of them as true.
• The first row dp[0][] indicates that only the first element of the array is considered, therefore for the target value equal to arr[0], only one cell with that target will be true, so explicitly set dp[0][arr[0]] =true, (dp[0][arr[0]] means that we are considering the first element of the array with the target equal to the first element itself). It can happen that arr[0]>target, so we first check if(arr[0]<=target) then set dp[0][arr[0]] = true.
• We then traverse two for loops and follow the condition formed to update values in DP as per our condition.
• At last we will return dp[n-1][k] as our answer.

Code:

bool canPartition(vector<int>& arr) {
    int totSum=0;
    int n = arr.size();
    for(int i=0; i<n;i++){
        totSum+= arr[i];
    }

    if (totSum%2==1) return false;

    else{
        int k = totSum/2;
        vector<vector<bool>> dp(n,vector<bool>(k+1,false));

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

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

        for(int ind = 1; ind<n; ind++){
            for(int target= 1; target<=k; target++){

                bool notTaken = dp[ind-1][target];

                bool taken = false;
                    if(arr[ind]<=target)
                        taken = dp[ind-1][target-arr[ind]];

                dp[ind][target]= notTaken||taken;
            }
        }

        return dp[n-1][k];

    } 
}

Time Complexity: O(N*K)
Space Complexity: O(N*K).

By Careful observation we see, that at every step we are applying this and storing this.
dp[index][target] = dp[ind-1][target] || dp[ind-1][target-nums[index]

Hence we can optimize it's space as we only require the last row at a time to calculate the result.

Space Optimization:

• Whenever we create a new row ( say cur), we need to explicitly set its first element is true according to our base condition.
• We can just initialize a vector and store the last row in that and update accordingly.

Code:

bool canPartition(vector<int>& arr) {
    int totSum=0;
    int n = arr.size();
    for(int i=0; i<n;i++){
        totSum+= arr[i];
    }

    if (totSum%2==1) return false;

    else{
        int k = totSum/2;
        vector<vector<bool>> dp(n,vector<bool>(k+1,false));

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

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

        for(int ind = 1; ind<n; ind++){
            for(int target= 1; target<=k; target++){

                bool notTaken = dp[ind-1][target];

                bool taken = false;
                    if(arr[ind]<=target)
                        taken = dp[ind-1][target-arr[ind]];

                dp[ind][target]= notTaken||taken;
            }
        }

        return dp[n-1][k];

    } 
}

Complexity Analysis:

Time Complexity: O(N*K)
Space Complexity: O(K)

Thanks for reading. Feedback and criticism are both equally appreciated.