416. Partition Equal Subset Sum

#dp

Problem

Partition Equal Subset Sum - LeetCodeLeetCode

Intuition

It is same as CN: Subset Sum Equal To K. The only extra constraint is if it can be partitioned into two equal halves. We sum the whole array, if total sum is odd then it cannot be evenly distributed and we will return false.

Then we take the totalSum/2 and search if we can find any subset whose target is equal to totalSum/2. If we find half sum then it means the rest of the elements make up the half sum and can be returned true;

Time and Space Complexity

I have already used the most optimised version for space.

• Time Complexity: O(N^K) traverse all the states

• Space Complexity: O(K+1) Store only the previous state values

Solution

class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for(int num: nums) {
            totalSum += num;
        }

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

        return tabulationSpaceOptimizationHelper(nums.length, totalSum/2, nums);
    }

     private boolean tabulationSpaceOptimizationHelper(int n, int k, int[] arr) {
        // Tabulation approach with space optimization using two boolean arrays.
        boolean[] prev = new boolean[k + 1]; // Array to store the previous row of the dp table.
        prev[0] = true; // Base case: An empty subset can form a sum of 0.
        
        // Base case: If the first element of arr is less than or equal to k, 
        // it is a valid subset
        if (arr[0] <= k) {
            prev[arr[0]] = true;
        }

        for (int idx = 1; idx < n; idx++) {
            // Array to store the current row of the dp table.
            boolean[] curr = new boolean[k + 1]; 
            // Base case: An empty subset can form a sum of 0.
            curr[0] = true; 
            for (int target = 1; target <= k; target++) {
                boolean notPick = prev[target];
                boolean pick = false;

                // Check if the current element arr[idx] can be picked
                if (arr[idx] <= target) {
                    pick = prev[target - arr[idx]];
                }

                // Either pick or not pick the current element
                curr[target] = pick || notPick;
            }
            // Update the previous row with the current row for the
            // next iteration.
            prev = curr;
        }

        // The result is stored at the last index of the prev array.
        return prev[k]; 
    }
}