Partition equal subset sum

XXX. Partition Equal Subset Sum

Dynamic Programming

Problem Statement:

Given an array of positive integers, determine if the array can be partitioned into two subsets such that the sums of the subsets are equal.

Return true if such a partition is possible, otherwise return false.

Algorithm:

1. Calculate the total sum of the array. If the sum is odd, it's impossible to partition into two equal subsets.
2. Reduce the problem to finding a subset of the array that sums to sum / 2.
3. Use a 1D dynamic programming array to track whether a specific sum can be achieved using the numbers in the array.
4. Traverse the array and update the DP array in reverse to avoid overwriting values needed for subsequent calculations.
5. Return the value of dp[sum / 2] to determine if the subset sum is achievable.

Complexity:

Time Complexity: O(n * sum), where n is the number of elements in the array and sum is the total sum divided by 2.
Space Complexity: O(sum), as a 1D DP array of size sum / 2 + 1 is used.

Java Implementation:

public boolean canPartition(int[] nums) { 
        // Exactly like subset sum but with sum / 2
        // Because if you can make sum / 2, then you definitely have the other subset making the total sum
        // Use 1D DP array for optimization
        int sum = 0;
        for (int num : nums) sum += num; // Calculate total sum of the array
        
        // If the sum is odd, it's impossible to partition equally
        if (sum % 2 != 0) return false;
        
        sum /= 2; // Target subset sum is half of the total sum
        boolean[] dp = new boolean[sum + 1]; // DP array to track achievable sums
        dp[0] = true; // Base case: a sum of 0 is always achievable
        
        // Traverse each number in the array
        for (int num : nums)
            // Update DP array in reverse to avoid overwriting results from the same iteration
            for (int j = sum; j >= num; j--) 
                dp[j] = dp[j] || dp[j - num]; // Update current sum using the current number
        
        return dp[sum]; // Check if target subset sum is achievable
    }

Explanation:

The problem is reduced to a subset sum problem where the goal is to find a subset that sums to sum / 2. This is solved efficiently using a 1D dynamic programming array:

• The DP array dp[j] tracks whether a sum j can be formed using the elements processed so far.
• By iterating the array in reverse (from sum to num), we ensure that each number is only used once in the subset.
• The final answer is given by dp[sum / 2], which indicates whether the target sum is achievable.