Partition Equal Subset Sum

Medium

💭 Introduction

You’re given an array of positive integers. Your task is to determine if you can partition the array into two subsets such that the sum of elements in both subsets is equal.

This is a classic 0/1 Knapsack variant — each element can either be included or excluded from a subset.

For example, if nums = [1, 5, 11, 5], you can partition it into [1, 5, 5] and [11], both with sum 11.

Your goal is to determine if such a partition exists.

🧩 Problem Statement

LeetCode #416 — Partition Equal Subset Sum

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

🔍 Example 1:

Input: nums = [1,5,11,5]
Output: true

Explanation:

The array can be partitioned as [1, 5, 5] and [11]. Both subsets have sum = 11.

🔍 Example 2:

Input: nums = [1,2,3,5]
Output: false

Explanation:

The array cannot be partitioned into equal sum subsets. Total sum = 11, which is odd, so equal partition is impossible.

🔍 Example 3:

Input: nums = [1,2,5]
Output: false

Explanation:

Total sum = 8, but no valid partition exists.

🧠 Step 1: Understanding the Problem

Let’s break down what we’re really asking:

If we can split the array into two equal-sum subsets, what must be true?

Key Insight:

• Total sum must be even (otherwise equal split is impossible)
• Each subset must have sum = total_sum / 2
• We only need to find one subset with sum = target
• The remaining elements automatically form the other subset!

Transform the problem:

"Can we partition into two equal subsets?"
        ↓
"Can we find a subset with sum = total_sum / 2?"

This is now a Subset Sum Problem — a classic 0/1 Knapsack variant!

🤔 Step 2: The Brute Force Approach

We could try all possible subsets and check if any has sum = target:

def canPartition(nums):
    total = sum(nums)
    
    # If total is odd, impossible to partition equally
    if total % 2 != 0:
        return False
    
    target = total // 2
    
    def backtrack(index, current_sum):
        if current_sum == target:
            return True
        if index >= len(nums) or current_sum > target:
            return False
        
        # Include current element
        if backtrack(index + 1, current_sum + nums[index]):
            return True
        
        # Exclude current element
        return backtrack(index + 1, current_sum)
    
    return backtrack(0, 0)

Problem: This explores all $2^n$ possible subsets!

⏱️ Time Complexity: $O(2^n)$

📦 Space Complexity: $O(n)$ for recursion stack

🚀 Step 3: Top-Down DP (Memoization)

We can cache results to avoid recomputing the same subproblems:

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        
        if total % 2 != 0:
            return False
        
        target = total // 2
        memo = {}
        
        def dp(index, remaining):
            # Base cases
            if remaining == 0:
                return True
            if index >= len(nums) or remaining < 0:
                return False
            
            # Check memo
            if (index, remaining) in memo:
                return memo[(index, remaining)]
            
            # Try including or excluding current element
            include = dp(index + 1, remaining - nums[index])
            exclude = dp(index + 1, remaining)
            
            memo[(index, remaining)] = include or exclude
            return memo[(index, remaining)]
        
        return dp(0, target)

State: (index, remaining_sum) — can we achieve remaining_sum using elements from index onwards?

⏱️ Time Complexity: $O(n \times \text{sum})$

📦 Space Complexity: $O(n \times \text{sum})$

⚙️ Step 4: Bottom-Up DP (Tabulation)

Let’s build a table from the ground up:

Define: dp[i][j] = can we achieve sum j using first i elements?

Recurrence relation:

dp[i][j] = dp[i-1][j]                    // Don't include nums[i-1]
           OR
           dp[i-1][j - nums[i-1]]        // Include nums[i-1]

Base cases:

dp[i][0] = True   // We can always make sum 0 (empty subset)
dp[0][j] = False  // Can't make any positive sum with 0 elements

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        
        if total % 2 != 0:
            return False
        
        target = total // 2
        n = len(nums)
        
        # dp[i][j] = can we make sum j using first i elements
        dp = [[False] * (target + 1) for _ in range(n + 1)]
        
        # Base case: sum 0 is always achievable
        for i in range(n + 1):
            dp[i][0] = True
        
        # Fill the table
        for i in range(1, n + 1):
            for j in range(1, target + 1):
                # Don't include current element
                dp[i][j] = dp[i-1][j]
                
                # Include current element if possible
                if j >= nums[i-1]:
                    dp[i][j] = dp[i][j] or dp[i-1][j - nums[i-1]]
        
        return dp[n][target]

Let’s trace through Example 1: nums = [1, 5, 11, 5], target = 11

i\j	0	1	2	3	4	5	6	7	8	9	10	11
0	T	F	F	F	F	F	F	F	F	F	F	F
1(1)	T	T	F	F	F	F	F	F	F	F	F	F
2(5)	T	T	F	F	F	T	T	F	F	F	F	F
3(11)	T	T	F	F	F	T	T	F	F	F	F	T
4(5)	T	T	F	F	F	T	T	F	F	F	T	T

Final answer: dp[4][11] = True ✓

⏱️ Time Complexity: $O(n \times \text{sum})$

📦 Space Complexity: $O(n \times \text{sum})$

🧮 Step 5: Space Optimization (1D DP)

Notice that dp[i][j] only depends on dp[i-1][...]. We can use a single array!

Key trick: Iterate j from right to left to avoid overwriting values we still need.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        
        if total % 2 != 0:
            return False
        
        target = total // 2
        
        # dp[j] = can we make sum j
        dp = [False] * (target + 1)
        dp[0] = True  # Base case: sum 0 is always achievable
        
        for num in nums:
            # Iterate backwards to avoid using updated values
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]
        
        return dp[target]

Why iterate backwards?

If we go forward, we might use dp[j - num] that was already updated in this iteration, effectively using the same element multiple times!

Going backwards ensures we only use values from the previous iteration.

⏱️ Time Complexity: $O(n \times \text{sum})$

📦 Space Complexity: $O(\text{sum})$ — Optimal!

🎯 Step 6: Alternative Approach - Using Set

We can track all possible sums we can achieve:

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        
        if total % 2 != 0:
            return False
        
        target = total // 2
        possible_sums = {0}  # Start with sum 0
        
        for num in nums:
            # Add all new sums we can make by including current number
            new_sums = set()
            for s in possible_sums:
                new_sums.add(s + num)
            possible_sums.update(new_sums)
            
            # Early termination
            if target in possible_sums:
                return True
        
        return target in possible_sums

This is essentially the same as 1D DP but using a set for clarity.

🎯 Key Insights

1. Problem transformation: Convert “partition into two equal subsets” to “find subset with sum = total/2”

2. Early termination: If total sum is odd, immediately return False

3. 0/1 Knapsack pattern: Each element can be included or excluded exactly once

4. Space optimization: Only need previous row’s values, so use 1D array

5. Backward iteration: When optimizing space, iterate backwards to avoid reusing elements

📊 Complexity Summary

Approach	Time	Space
Brute Force	$O(2^n)$	$O(n)$
Memoization	$O(n \times \text{sum})$	$O(n \times \text{sum})$
2D Tabulation	$O(n \times \text{sum})$	$O(n \times \text{sum})$
1D Tabulation	$O(n \times \text{sum})$	$O(\text{sum})$
Set Approach	$O(n \times \text{sum})$	$O(\text{sum})$

Where sum = sum of all elements in the array

🌟 Edge Cases to Consider

1. Empty array: [] → False (or True depending on definition)
2. Single element: [1] → False (can’t partition into two subsets)
3. Two equal elements: [1, 1] → True
4. Odd total sum: [1, 2, 3] → False (sum = 6, but no valid partition)
5. Large numbers: Consider integer overflow in other languages

💡 Common Mistakes

1. Forgetting odd sum check: Always check if total sum is odd first
2. Wrong iteration direction: In 1D DP, must iterate backwards
3. Off-by-one errors: Be careful with array indices and loop bounds
4. Not handling edge cases: Empty array, single element, etc.

🔍 Variations of This Problem

1. Partition to K Equal Sum Subsets — Generalization to K subsets
2. Minimum Subset Sum Difference — Minimize difference between two subsets
3. Target Sum — Assign +/- to each number to reach target
4. Last Stone Weight II — Similar subset sum optimization

💡 Related Problems

• House Robber - Linear DP pattern
• Maximum Subarray - Array optimization
• 0/1 Knapsack - The parent problem
• Subset Sum - Direct variant
• Coin Change - Similar DP pattern

🏆 Why This Problem Matters

1. Interview favorite: Common in FAANG interviews
2. 0/1 Knapsack mastery: Teaches the fundamental pattern
3. Space optimization: Shows how to reduce from 2D to 1D
4. Problem transformation: Teaches how to simplify complex problems
5. Real-world applications: Resource allocation, load balancing

🎓 Key Takeaways

• Recognize the pattern: “Partition into equal parts” → Subset Sum → 0/1 Knapsack
• Optimize progressively: Start with recursion, add memoization, then tabulation, finally space optimization
• Think in states: What information do we need to make a decision at each step?
• Early termination: Check for impossible cases before expensive computation