Partition equal subset sum

Divide the array in two parts and check if they can have same 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 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

Solution

The solution is very similar to what we did in previous question. Here we need to divide the array in two parts. So we'll basically search for sum/2 in array if it is found we can return true .

Memorization

var canPartition = function(nums) {

    let totalSum= nums.reduce((sum,num)=> sum+num);
        let n=nums.length;
    let len=(totalSum/2) +1
   


    if(totalSum%2 !==0){
        return false;
    }
     let dp= Array.from({length:n},()=>Array(len))
    function recurr(index,remaining,dp){

        if(remaining==0){
            return true;
        }

        if(index===0){
            return nums[0] ===remaining
        }

        if(dp[index][remaining] !==undefined){
            return dp[index][remaining];
        }

        let notTaken= recurr(index-1,remaining,dp);

        let taken = false;

        if(nums[index]<=remaining){

            taken = recurr(index-1, remaining - nums[index],dp);
        }

       dp[index][remaining]= notTaken || taken

       return dp[index][remaining]

    }

    return recurr(n-1,totalSum/2,dp)
    
};

Tabulation

var canPartition = function (nums) {

    let totalSum = nums.reduce((sum, num) => sum + num);
    let n = nums.length;
    let len = (totalSum / 2) + 1



    if (totalSum % 2 !== 0) {
        return false;
    }
    let dp = Array.from({ length: n }, () => Array(len).fill(false))

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

    dp[0][nums[0]] = true;

    let requiredSum = totalSum / 2;

    for (let index = 1; index < n; index++) {

        for (let sum = 1; sum <= requiredSum; sum++) {

            let notPick = dp[index - 1][sum];


            let pick = false;


            if (nums[index] <= sum) {
                pick = dp[index - 1][sum - nums[index]]
            }

            dp[index][sum] = pick || notPick
        }
    }



    return dp[n - 1][requiredSum];

};