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 . With N up to 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 complexity where is the target sum.
Approach
- Calculate Total Sum: Iterate through
numsto find the total sum. If this sum is odd, returnFalseimmediately because equal partitioning requires an even total sum. - Define Target: Set our goal as finding a subset that sums up to
target = total_sum // 2. - Initialize DP State: Create a boolean array (or set) of size
target + 1. Initialize index0toTrue, representing that a sum of 0 is always possible with an empty subset. All other indices are initiallyFalse. - 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
targetdown to the value of the current number. This ensures that when calculating if sumjis 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 makesdp[j]possible as well.
Complexity Analysis
- Time Complexity: , where is the number of elements and is half the total sum (). Given constraints (, max element ), operations are roughly proportional to , which easily fits within time limits.
- Space Complexity: for the DP array of size
target + 1. This is significantly smaller than storing all subsets or a full matrix (), 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 != 0at the start and returnsFalse, preventing unnecessary computation. - Single Element Array: If input is
[x], sum isx. Target isx // 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 returnsFalsebecause the loop won’t reach indextargetifnum > 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).