Partition Equal Subset Sum | Leetcode 416

This problem is a direct extension of the Subset Sum Problem: instead of checking if any subset sums to a given target, here we check if the array can be split into two subsets with equal sum. That is equivalent to asking: is there a subset whose sum is exactly half of the total array sum?

Here’s the [Problem Link] to begin with.

What Does the Problem Say?

Given an array nums of positive integers, determine whether it can be partitioned into two subsets whose sums are equal. This is possible only if:

• The total sum is even (otherwise, halves are not integers).
• There exists a subset that sums to total_sum / 2.

Key Insight

Let total = sum(nums). If total is odd, return False immediately. Otherwise, define k = total // 2 and solve “is there a subset with sum k?”, which is precisely the Subset Sum DP you solved earlier.

Space-Optimized Tabulation (Bottom-Up 1D DP)

Intuition and Approach

We reuse the Subset Sum DP idea:

• prev[t] tells whether a subset from the processed prefix can achieve sum t.
• Initialize prev = True (empty subset makes sum 0).
• Seed with the first element if it’s ≤ k.
• For each number, compute a new curr over all targets t in [0..k]:
  • pick = prev[t – nums[i]] if nums[i] ≤ t else False
  • not_pick = prev[t]
  • curr[t] = pick or not_pick
• After processing all elements, check prev[k].

Why 1D rolling array? Each row depends only on the previous row, so we keep two 1D arrays (prev and curr), achieving O(k) space.

Code Implementation

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        target = sum(nums)
        # Total must be even to split into two equal subsets
        if target % 2 == 1:
            return False
        k = target // 2
        prev = [False for _ in range(k + 1)]
        prev = True  # Sum 0 is always achievable (empty subset)
        if nums <= k:
            prev[nums] = True  # Seed with first element if within target
        for index in range(1, n):
            curr = [False for _ in range(k + 1)]
            for target in range(0, k + 1):
                # Option 1: pick current number if it doesn't exceed target
                if nums[index] > target:
                    pick = False
                else:
                    pick = prev[target - nums[index]]
                # Option 2: do not pick current number
                not_pick = prev[target]
                # Achievable if either pick or not_pick is True
                curr[target] = pick or not_pick
            prev = curr  # Move window to next element
        if prev[k] == True:
            return True
        return False

Code Explanation

• Early exit on odd total sum.
• Convert to subset sum: target k = total/2.
• prev represents achievable sums after processing the current prefix.
• For each element, curr aggregates new achievable sums using pick/not-pick transitions.
• Final answer is whether k is achievable after all elements.

Time and Space Complexity

• Precise: Time O(n × k), Space O(k), where k = total_sum / 2.
• Simplified: Pseudo-polynomial time; linear space in target.

Why It’s an Extension of Subset Sum

• Subset Sum asks: is there a subset equal to S?
• Partition Equal Subset Sum asks: can we split the array into two equal halves? That’s equivalent to checking if a subset equals total_sum/2.
• Hence, the same DP structure applies, and the space-optimized 1D DP is the most practical solution.

Conclusion

Partition Equal Subset Sum is a clean application of the Subset Sum DP with a simple parity check up front. Use the O(n × k) time and O(k) space rolling-array DP to pass all constraints efficiently. This pattern generalizes well to many related partitioning and knapsack-style problems.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.