Partition Equal Subset Sum

How it works

This is the most optimal DP solution for Partition Equal Subset Sum.

We reduce the problem to:

Can we pick some numbers whose sum equals target = total_sum / 2?

We use a 1D DP array where:

• dp[j] = True means we can form sum j using some of the numbers so far.

Key idea:

• For each number, update the DP from right to left so that each number is used only once.
• This avoids overwriting results from the same iteration.

Steps

1. Compute total = sum(nums). If total is odd, return false.
2. Set target = total // 2.
3. Create a boolean array dp of size target + 1.
   • Initialize dp[0] = true (sum 0 is always achievable).
4. For each number num in nums:
   • Traverse j from target down to num:
     • Set dp[j] = dp[j] OR dp[j - num]
5. Return dp[target].

Complexity

• Time complexity: O(n * target)
• Space complexity: O(target)

Where n is the length of the array nums and target is the sum of array elements divided by 2.

Things to watch for

Forgetting the Odd Sum Check

The most common mistake is forgetting to check if the total sum is odd before proceeding. If sum(nums) is odd, it's impossible to split into two equal subsets, and you should immediately return false. Skipping this check leads to incorrect results or wasted computation.

Using Left-to-Right Iteration in Space-Optimized DP

When using a 1D DP array, iterating from left to right causes elements to be counted multiple times in the same iteration. You must iterate from right to left (target down to num) to ensure each element is used at most once per subset, preserving the 0/1 knapsack property.

Integer Overflow in Target Calculation

For languages without arbitrary precision integers, the sum of array elements can overflow if not handled carefully. Always use appropriate data types (like long in Java/C++) when computing the total sum before dividing by 2 to get the target.

class Solution:
    def canPartition(self, nums: list[int]) -> bool:
        if sum(nums) % 2:
            return False

        target = sum(nums) // 2
        dp = [False] * (target + 1)

        dp[0] = True
        for num in nums:
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]

        return dp[target]

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        if (sum(nums) % 2 != 0) {
            return false;
        }

        int target = sum(nums) / 2;
        vector<bool> dp(target + 1, false);

        dp[0] = true;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }

        return dp[target];
    }

private:
    int sum(vector<int>& nums) {
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        return total;
    }
};