DP 15. Partition Equal Subset Sum | DP on Subsequences

This chapter explores how to partition a given array of positive integers into two subsets such that the sum of elements in both subsets is equal. Building directly upon the foundation laid in Lecture 14 (Subset Sum Equal to Target), this problem transforms from a brand-new challenge into a clever reduction exercise.

1. Problem Statement & The Core Challenge

You are given an array of $N$ positive integers. Your objective is to determine whether you can split this array into two distinct subsets such that:

Example Walkthrough

Consider the input array: [2, 3, 3, 4, 5]

If we divide the elements into two groups:

• Subset 1: [2, 3, 5] $\rightarrow \text{Sum} = 10$
• Subset 2: [3, 3, 4] $\rightarrow \text{Sum} = 10$

Both subsets achieve an identical sum of $10$. Therefore, the function should return true.

2. Real-Life Analogy: Splitting a Bill or Inventory

Real-Life Analogy: Imagine you and a business partner share a pile of inventory items of varying weights, and you want to split the inventory equally into two storage rooms so that the total weight in Room A matches the total weight in Room B down to the exact pound.

Instead of trying to balance both rooms simultaneously, you realize that if the total weight of all items is $20\text{ lbs}$, your goal is simply to pack one room with items totaling $10\text{ lbs}$. Once you successfully pack Room A to $10\text{ lbs}$, the remaining items left over are mathematically guaranteed to weigh $10\text{ lbs}$ and automatically fill Room B.

3. Mathematical Reduction: Simplifying to Lecture 14

Let $S$ represent the total sum of all elements in the entire array. When we divide the array into two subsets with sums $S_1$ and $S_2$:

• $S_1 + S_2 = S$
• $S_1 = S_2$ (given by the problem condition)

Substituting $S_1$ for $S_2$:

This leads to two crucial logical deductions:

1. The Odd Sum Rule: If the total sum $S$ is an odd number, it is impossible to divide it into two equal integer subsets. We can immediately return false.
2. The Target Reduction: If $S$ is even, the problem instantly reduces to: "Can we find a subsequence whose sum equals $\frac{S}{2}$?"

4. Architectural Flow of the Solution

5. Implementation Evolution

Naive vs. Optimized Approach

We do not need to rewrite dynamic programming tabulation or space-optimization tables from scratch. Because Lecture 14 solved Subset Sum Equal to Target, we can directly invoke that logic by passing Target = S / 2.

Below is the complete C++ implementation incorporating the check for total sum parity and utilizing the space-optimized subset sum function:

class Solution {
public:
    bool subsetSum(int n, int k, vector<int>& arr) {
        vector<bool> prev(k + 1, false);
        
        // Base case: A sum of 0 is always possible with an empty subset
        prev[0] = true;
        
        // If the first element is less than or equal to target k, mark its index as true
        if (arr[0] <= k) {
            prev[arr[0]] = true;
        }
        
        for (int ind = 1; ind < n; ind++) {
            vector<bool> curr(k + 1, false);
            curr[0] = true; // Sum 0 is always possible
            
            for (int target = 1; target <= k; target++) {
                bool notTaken = prev[target];
                bool taken = false;
                if (arr[ind] <= target) {
                    taken = prev[target - arr[ind]];
                }
                curr[target] = notTaken || taken;
            }
            prev = curr;
        }
        return prev[k];
    }

    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int totalSum = 0;
        
        // Step 1: Calculate total sum of the array
        for (int i = 0; i < n; i++) {
            totalSum += nums[i];
        }
        
        // Step 2: If total sum is odd, equal partition is impossible
        if (totalSum % 2 != 0) {
            return false;
        }
        
        // Step 3: Target is half of the total sum
        int target = totalSum / 2;
        
        // Step 4: Check if subset with sum equal to target exists
        return subsetSum(n, target, nums);
    }
};

6. Critical Edge Cases & Debugging Notes

1. Array Element Exceeding Target (arr[0] <= k):
   • In space-optimized DP arrays of size k + 1, initializing prev[arr[0]] = true can trigger an out-of-bounds error if arr[0] is strictly greater than target k.
   • Correction: Always verify that arr[0] <= k before assigning prev[arr[0]] = true.
2. All Positive Integers:
   • The constraints specify positive integers. If zeroes are present, subset sum logic still holds, but negative numbers require entirely different algorithmic handling (e.g., partitioning with negative values alters the subset sum monotonic property).

7. Complexity Analysis

Summary and Key Takeaways

• Problem Reduction: Partition Equal Subset Sum is not a new pattern; it is a direct application of the Subset Sum Equal to Target problem (Lecture 14).
• The Parity Check: If the total sum $S$ of the array is odd, return false instantly because integers cannot be split into two equal halves.
• Target Definition: The search target for the subset sum function is precisely half of the total sum ($\frac{S}{2}$). Finding one subset with sum $\frac{S}{2}$ automatically ensures the remaining elements form the second subset of equal sum.
• Space Optimization: By leveraging space-optimized 1D arrays from Lecture 14, we maintain an optimal $O(\text{Target})$ space complexity.
• Initialization Safety: Always guard array indexing against targets when initializing base cases (e.g., ensuring arr[0] <= k before setting DP state).