Partition Equal Subset Sum

Problem Statement

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 1:

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

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

• 1 <= nums.length <= 200

• 1 <= nums[i] <= 100

Intution - We have to divide the array target in two parts

Let say if the total sum of array is 20-> 
then we just need to find, If there exists a subset having a sum of target of 10

That is sum/2 

Now if the total sum is odd we cannot divide the sum , hence directly false

Links

Partition Equal Subset Sum - LeetCodeLeetCode

Video Link

https://www.youtube.com/watch?v=7win3dcgo3k&ab_channel=takeUforward

Approach 1:

Memoization

C++

class Solution {
public:
    bool subsum(vector<int>& nums, int target, int index, vector<vector<int>> &dp){
        if(target == 0)
            return true;

        if(index == 0)
            return nums[0] == target;

        if(dp[index][target] != -1)
            return dp[index][target]; 

        bool not_take = subsum(nums,target, index-1,dp);

        bool take = false;
        if(target >= nums[index])
            take = subsum(nums, target- nums[index], index-1,dp);

        return dp[index][target] = take or not_take;
    }

    bool canPartition(vector<int>& nums) {
        int target = accumulate(nums.begin(), nums.end(), 0);
        int n = nums.size();
        
        if(target % 2 != 0)
            return false;
        
        vector<vector<int>> dp(n, vector<int>(target/2+1, -1));

        return subsum(nums, target/2, n-1,dp);
    }
};

Approach 2:

Tabulation

C++

bool canPartition(vector<int>& arr) {
        int sum = accumulate(arr.begin(), arr.end(), 0);
        int n = arr.size();
        
        if(sum % 2 != 0)
            return false;

        int target = sum/2;
        
        vector<vector<bool>> dp(n, vector<bool>(target+1, false));

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

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

        for(int index=1; index<n; index++){
            for(int tar=1; tar<=target; tar++){
                bool not_take = dp[index-1][tar];

                bool take = false;
                if(tar>=arr[index])
                    take = dp[index-1][tar-arr[index]];

                dp[index][tar] = take or not_take;
            }
        }

        return dp[n-1][target];
    }

Approach 3:

Space Optimize

C++

class Solution {
public:
    bool canPartition(vector<int>& arr) {
        int sum = accumulate(arr.begin(), arr.end(), 0);
        int n = arr.size();
        
        if(sum % 2 != 0)
            return false;

        int target = sum/2;
        
        vector<bool> dp(target+1, false);
        dp[0] = true;
        

        for(int index=1; index<n; index++){
            vector<bool> temp(target+1, false);
            temp[0] = true;

            for(int tar=1; tar<=target; tar++){
                bool not_take = dp[tar];

                bool take = false;
                if(tar>=arr[index])
                    take = dp[tar-arr[index]];

                temp[tar] = take or not_take;
            }
            dp = temp;
        }

        return dp[target];
    }
};

Similar Problems