Skip to content

Leetcode 416 - Partition Equal Subset Sum

Understanding the Problem

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.

Return:

  • True if a valid partition exists.
  • False if it is impossible to split into two equal-sum subsets.

Key Data Structures

1. Hash Set (dp)

A dynamic set used to store all possible distinct subset sums attainable using elements processed so far.

2. Dynamic Programming Table / Array

An alternative implementation tool (1D boolean array) where dp[i] represents whether a subset sum of i is achievable.

Optimal Approach Intuition

This problem reduces to the 0/1 Knapsack Problem:

  • Total Target: If sum(nums) is odd, equal partition is mathematically impossible. If even, the target subset sum is target = total_sum // 2.
  • Decision: For each number in nums, decide whether to include it in the subset or exclude it.
  • Goal: Find if there exists any combination of numbers that sums exactly to target.

Why 0/1 Knapsack (DP) over Plain DFS?

1. Exponential Complexity of Plain DFS

The naive DFS recursive approach explores all \(2^n\) subsets. Without memoization/DP, this causes Time Limit Exceeded (TLE) for larger inputs.

2. Overlapping Subproblems and Optimal Substructure

Different subsets can yield the same intermediate sum (e.g., [1, 4] and [2, 3] both sum to 5). Using dynamic programming lets us store unique achievable sums, avoiding duplicate computations and scaling efficiently relative to the target sum.

How the Optimal Approach Works

Step 1: Early Rejection

Check if sum(nums) is odd. If odd, return False immediately. Compute target = sum(nums) // 2.

Step 2: DP State Transitions (Set-Based)

Initialize a set dp = {0} (representing the initial base case sum of 0).

Iterate through each number n in nums: 1. Create a new temporary set next_dp. 2. For each existing sum t in dp: - Keep t (exclude n). - Add t + n (include n). 3. If target is in next_dp, return True early. 4. Update dp = next_dp.

Solution Implementation

1. Naive Brute Force (DFS - TLE)

from typing import List


class Solution:

    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)

        if total_sum % 2 != 0:
            return False

        target = total_sum // 2

        def dfs(idx, curr_sum):
            if curr_sum == target:
                return True
            if idx >= len(nums) or curr_sum > target:
                return False

            return dfs(idx + 1, curr_sum + nums[idx]) or dfs(idx + 1, curr_sum)

        return dfs(0, 0)

2. Optimal Approach (Dynamic Programming - Hash Set)

from typing import List


class Solution:

    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)

        # Early exit if sum is odd
        if total_sum % 2 != 0:
            return False

        target = total_sum // 2
        dp = set([0])

        for num in nums:
            next_dp = set()
            for t in dp:
                if t + num == target:
                    return True
                if t + num < target:
                    next_dp.add(t + num)
                next_dp.add(t)
            dp = next_dp

        return target in dp

Complexity Analysis

Let:

  • \(N\) = Length of nums
  • \(S\) = sum(nums) // 2 (Target subset sum)

Time Complexity: \(O(N \times S)\)

  • Sum Calculation: \(O(N)\) to calculate total sum.
  • DP Iteration: Outer loop runs \(N\) times. The inner set holds at most \(S\) distinct sums.

Overall Time Complexity: \(O(N \times S)\)

Space Complexity: \(O(S)\)

  • Hash Set (dp): Holds at most \(S\) distinct target sums in the range \([0, target]\).

Overall Space Complexity: \(O(S)\)

Key Takeaways

  • Reduction to Knapsack: Subsets with equal sums equal finding a single subset summing to \(\text{total\_sum} / 2\).
  • Odd Sum Short-Circuit: If total sum is odd, integer division cannot divide it evenly, allowing an instant \(O(1)\) exit.
  • Space-Efficient DP Set: Using a set automatically deduplicates redundant intermediate path sums.

Common Mistakes

Mistake 1: Not Pruning Sums Beyond Target

Adding values greater than target into the DP state needlessly inflates space and execution time.

Fix:

  • Only store next sums where t + num <= target.

Mistake 2: Modifying DP Set While Iterating

Modifying dp directly during iteration leads to runtime set modification errors or processing the same element multiple times within one step.

Fix:

  • Build a new next_dp set during each outer loop iteration, or iterate backwards when using a 1D DP array.

Mistake 3: Floating Point Operations

Using float division (total_sum / 2) can introduce floating-point inaccuracies.

Fix:

  • Use integer division (total_sum // 2).

Additional Resources