#110 Medium Time O(n·sum) Space O(sum) Animated

Partition Equal Subset Sum

Determine if array can be partitioned into two equal-sum subsets.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Dynamic programming: reuse smaller answers

Define one state whose value fully solves a smaller version of the problem.

Approach: Dynamic Programming (1D)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Define one state whose value fully solves a smaller version of the problem.

Common Pitfall

Write the recurrence in words before optimizing the storage.

Description

Determine if array can be partitioned into two equal-sum subsets.

Constraints

Time Complexity: O(n·sum)
Space Complexity: O(sum)

Solution — Dynamic Programming (1D)

TimeO(n·sum) SpaceO(sum)

Implementation Plan

Translate the invariant into these small, testable moves.

Define the state precisely.
Set base cases.
Fill states in dependency order.
Return the final state.

def canPartition(nums):
    if sum(nums) % 2:
        return False
        
    dp = set()
    dp.add(0)
    target = sum(nums) // 2
    
    for i in range(len(nums) - 1, -1, -1):
        nextDP = set()
        for t in dp:
            if (t + nums[i]) == target:
                return True
            nextDP.add(t + nums[i])
            nextDP.add(t)
        dp = nextDP
        
    return True

Longest Increasing Subsequence

Partition Equal Subset Sum

Steps

Description

Constraints

Tags

Solution — Dynamic Programming (1D)