LeetCode 416: Partition Equal Subset Sum Solution in Python – A Step-by-Step Guide

What Is LeetCode 416: Partition Equal Subset Sum?

In LeetCode 416: Partition Equal Subset Sum, you’re given an array nums of positive integers (e.g., [1, 5, 11, 5]), and you need to determine if you can split it into two non-empty subsets with equal sums. The total sum must be even for this to be possible (e.g., 22 splits into 11 + 11). If it works, return True; if not, False. For [1, 5, 11, 5], the answer is True because [1, 5, 5] and [11] both sum to 11. It’s like a knapsack problem where you’re aiming for half the total weight.

Problem Statement

• Input: An integer array nums.
• Output: A boolean—True if nums can be partitioned into two subsets with equal sums, False otherwise.
• Rules:
• Subsets must be non-empty and contiguous or non-contiguous.
• Total sum must be even for a valid split.

Constraints

• 1 <= nums.length <= 200.
• 1 <= nums[i] <= 100.

Examples

• Input: nums = [1,5,11,5]
• Output: True (e.g., [1,5,5] and [11], both sum to 11).
• Input: nums = [1,2,3,5]
• Output: False (sum 11, no way to get 5.5).
• Input: nums = [1,2,3,4]
• Output: False (sum 10, subsets like [1,4] = 5 exist, but no pair matches).

Understanding the Problem: Splitting the Sum

To solve LeetCode 416: Partition Equal Subset Sum in Python, we need to check if nums can be divided into two subsets summing to half the total (if the total is even). A naive idea might be to try every possible subset—but with up to 200 elements, that’s 2²⁰⁰ possibilities! Instead, we’ll use:

• Best Solution (DP with 1D Array): O(n * sum) time, O(sum) space—finds a subset sum efficiently.
• Alternative Solution (Recursive with Memoization): O(n * sum) time, O(n * sum) space—explores recursively.

Let’s dive into the DP solution with a clear, step-by-step explanation.

Best Solution: Dynamic Programming with 1D Array

Why This Is the Best Solution

The dynamic programming with a 1D array method is the top pick because it’s efficient—O(n * sum) time, O(sum) space—and simplifies the problem into a subset sum check. It uses a boolean array to track which sums are possible up to half the total, updating as it includes each number. It’s like filling a piggy bank to exactly half the goal, seeing if you can hit the mark!

How It Works

Think of the array as coins you’re picking:

• Step 1: Check Total Sum:
• Sum nums (e.g., 22 for [1,5,11,5]).
• If odd, return False (can’t split evenly).
• Target = sum // 2 (e.g., 11).
• Step 2: Set Up DP Array:
• dp[j] = True if sum j is possible with some subset.
• Start: dp[0] = True (empty subset sums to 0).
• Step 3: Fill DP:
• For each number, update dp from right to left:
• If dp[j - num] is True, dp[j] becomes True (can add num to reach j).
• Step 4: Check Target:
• Return dp[target] (e.g., dp[11] = True → possible).
• Step 5: Why This Works:
• Reduces to finding one subset with sum = total/2.
• 1D array saves space by reusing states.
• It’s like checking if you can pack half the coins perfectly!

Step-by-Step Example

Example: nums = [1,5,11,5]

• Sum: 1 + 5 + 11 + 5 = 22, target = 11.
• DP: dp[0..11] = [True, False, ..., False].
• Num 1: dp[1] = True (0+1), dp = [T, T, F, ..., F].
• Num 5: dp[6] = True (1+5), dp[5] = True (0+5), dp = [T, T, F, F, F, T, T, F, ..., F].
• Num 11: dp[11] = True (0+11), dp = [T, T, F, F, F, T, T, F, F, F, F, T].
• Num 5: dp[11] = True (6+5), dp[10] = True (5+5), dp[5] = True (0+5), dp = [T, T, F, F, F, T, T, F, F, F, T, T].
• Result: dp[11] = True, return True.

Example: nums = [1,2,3,5]

• Sum: 11, odd, return False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # Step 1: Check total sum
        total = sum(nums)
        if total % 2 != 0:  # Odd sum, can't split evenly
            return False
        target = total // 2

        # Step 2: Initialize DP array
        dp = [False] * (target + 1)
        dp[0] = True  # Empty subset sums to 0

        # Step 3: Process each number
        for num in nums:
            # Update from right to left
            for j in range(target, num - 1, -1):
                if dp[j - num]:  # Can reach j-num, now reach j
                    dp[j] = True

        # Step 4: Check if target sum is possible
        return dp[target]

• Line 4-7: Sum and validate:
• total: Sum of nums (e.g., 22).
• If odd, return False.
• target: Half the sum (e.g., 11).
• Line 10-11: Set up dp:
• Size target + 1 (0 to 11).
• dp[0] = True (base case).
• Line 14-17: Loop through nums:
• Line 15-17: For each sum j from target to num:
• If dp[j - num] is True, set dp[j] = True (e.g., dp[5] → dp[6] with 1).
• Line 20: Return dp[target] (e.g., dp[11]).
• Time Complexity: O(n * sum)—n numbers, sum/2 iterations.
• Space Complexity: O(sum)—dp array size.

This is like filling a coin jar to exactly half the total!

Alternative Solution: Recursive with Memoization

Why an Alternative Approach?

The recursive with memoization method explores all subset possibilities, caching results to avoid rework. It’s O(n * sum) time and O(n * sum) space—more intuitive but heavier on memory. It’s like trying every combination of coins until you hit half the jackpot!

How It Works

Picture it as picking coins:

• Step 1: Check sum, target = sum/2.
• Step 2: Recurse with index and remaining sum:
• Take current number, reduce sum.
• Skip current number, keep sum.
• Step 3: Memoize (index, sum) pairs.

Step-by-Step Example

Example: nums = [1,5,11,5]

• Sum: 22, target = 11.
• (0, 11): Take 1 → (1, 10), Skip → (1, 11).
• (1, 10): Take 5 → (2, 5), Skip → (2, 10).
• (2, 5): Take 11 fails, Skip → (3, 5).
• (3, 5): Take 5 → (4, 0), True.
• Result: True.

Code for Recursive Approach

Copy codeclass Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        target = total // 2

        memo = {}

        def dfs(index, remaining):
            if remaining == 0:
                return True
            if index >= len(nums) or remaining < 0:
                return False
            if (index, remaining) in memo:
                return memo[(index, remaining)]

            # Take or skip current number
            take = dfs(index + 1, remaining - nums[index])
            skip = dfs(index + 1, remaining)
            memo[(index, remaining)] = take or skip
            return memo[(index, remaining)]

        return dfs(0, target)

• Time Complexity: O(n * sum)—memoized states.
• Space Complexity: O(n * sum)—memo dictionary.

It’s a coin-picking explorer!

Comparing the Two Solutions

• DP with 1D Array (Best):
• Pros: O(n * sum), O(sum), fast and lean.
• Cons: Less intuitive.
• Recursive with Memo (Alternative):
• Pros: O(n * sum), O(n * sum), clear exploration.
• Cons: More space.

DP wins for efficiency.

Additional Examples and Edge Cases

• [1]: False (sum 1, odd).
• [2,2]: True (2 + 2 = 2).
• [1,2,5]: False (sum 8, no 4).

DP handles all.

Complexity Breakdown

• DP: Time O(n * sum), Space O(sum).
• Recursive: Time O(n * sum), Space O(n * sum).

DP’s the champ.

Key Takeaways

• DP: Fill the target!
• Recursive: Explore it out!
• Partitions: Balance is key.
• Python Tip: Arrays rock—see [Python Basics](/python/basics).

Final Thoughts: Split That Sum

LeetCode 416: Partition Equal Subset Sum in Python is a balancing act. DP with 1D array nails it fast, while recursive memo explores every path. Want more DP fun? Try LeetCode 494: Target Sum or LeetCode 518: Coin Change II. Ready to partition? Head to Solve LeetCode 416 on LeetCode and balance that sum today!