Domain 2MediumCORE

Partition Equal Subset Sum

We are given a list of positive integers nums. The goal is to determine if we can partition this array into two subsets such that their sums are exactly equal.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming

416. Partition Equal Subset Sum

Model: qwen3.5:9b
Topics: Dynamic Programming
FAANG asked: 1
Acceptance rate: 45.0%


Problem Breakdown

We are given a list of positive integers nums. The goal is to determine if we can partition this array into two subsets such that their sums are exactly equal.

Inputs: A non-empty list of positive integers (1 <= nums[i]).
Outputs: Boolean value (True or False).

Key Constraints & Edge Cases:

  • Sum Parity: If the total sum of all elements is odd, it is mathematically impossible to split them into two equal integer sums. This allows for an immediate optimization (early exit).
  • Target Sum: We are essentially looking for a subset that sums up to exactly total_sum / 2. The remaining elements will automatically form the second half with the same sum.
  • Data Bounds: With length ≤ 200 and max value ≤ 100, the maximum possible total sum is 20,000. This fits comfortably within standard integer limits and memory constraints for a DP array of this size.

Intuition

Initially, one might consider generating all possible subsets using recursion or backtracking to check if any subset sums to total_sum / 2. However, the number of subsets is O(2N)O(2^N). With N up to 200, 22002^{200} is computationally infeasible.

The key insight here is recognizing this as a variation of the Subset Sum Problem (or specifically, the 0/1 Knapsack problem where we only care about reachability). We don’t need to track which elements form the subset; we only need to know if a specific sum s is achievable using any combination of items seen so far.

This transforms the state space from exponential (subsets) to polynomial based on the target value and number of items, allowing us to use Dynamic Programming with O(N⋅S)O(N \cdot S) complexity where SS is the target sum.

Approach

  1. Calculate Total Sum: Iterate through nums to find the total sum. If this sum is odd, return False immediately because equal partitioning requires an even total sum.
  2. Define Target: Set our goal as finding a subset that sums up to target = total_sum // 2.
  3. Initialize DP State: Create a boolean array (or set) of size target + 1. Initialize index 0 to True, representing that a sum of 0 is always possible with an empty subset. All other indices are initially False.
  4. Iterate and Update: For each number in nums:
    • We want to update our reachable sums based on the current item.
    • To avoid using the same item multiple times for a single sum calculation within one iteration (which would violate the “subset” constraint), we must iterate backwards from target down to the value of the current number. This ensures that when calculating if sum j is reachable, we only use data from the previous state (dp[j - num]).
    • Update logic: If dp[j - num] was previously possible (True), then adding the current item makes dp[j] possible as well.

Complexity Analysis

  • Time Complexity: O(N⋅S)O(N \cdot S), where NN is the number of elements and SS is half the total sum (≤10,000\le 10,000). Given constraints (N=200N=200, max element 100100), operations are roughly proportional to 200×10,000=2×106200 \times 10,000 = 2 \times 10^6, which easily fits within time limits.
  • Space Complexity: O(S)O(S) for the DP array of size target + 1. This is significantly smaller than storing all subsets or a full matrix (N⋅SN \cdot S), as we optimize space by using only one row (or column) at a time via backward iteration.

Solution

class Solution:
    def canPartition(self, nums):
        # Calculate total sum to check parity and determine target
        total_sum = sum(nums)
        
        # If odd, cannot be partitioned into two equal integer sums
        if total_sum % 2 != 0:
            return False
        
        target = total_sum // 2
        
        # dp[i] will store whether a subset with sum 'i' is possible
        # Initialize boolean array of size target + 1
        dp = [False] * (target + 1)
        
        # Base case: A sum of 0 is always achievable (empty set)
        dp[0] = True
        
        for num in nums:
            # Iterate backwards to ensure we don't use the same item 
            # multiple times for a single subset calculation within this step.
            # We only need to check indices down from target up to 'num'.
            for i in range(target, num - 1, -1):
                if dp[i - num]:
                    dp[i] = True
        
        return dp[target]

Edge Cases Handled

  • Odd Total Sum: The code checks total_sum % 2 != 0 at the start and returns False, preventing unnecessary computation.
  • Single Element Array: If input is [x], sum is x. Target is x // 2. Since elements are positive, a single element cannot form two equal non-zero sums (unless x=0 which isn’t allowed by constraints). The logic correctly returns False because the loop won’t reach index target if num > target.
  • Large Values: Constraints limit max sum to 20,000. A boolean list of this size is negligible memory usage (~16KB), avoiding overflow or Memory Limit Exceeded errors common in languages with smaller integer limits (though Python handles large ints automatically).