Partition Equal Subset Sum

LeetCode 416 • Medium • 0/1 Knapsack DP

Return true if you can partition nums into two subsets with equal sum (classic subset sum / 0–1 knapsack on booleans).

TimeO(n·sum)

SpaceO(sum)

Step0/0

Ready

dp[j] = can we form sum j with a subset? Iterate each number; update j downward.

Speed:

Whiteboard

Size:3

Type It

Subset sum to target = sum/2

dp[0]=True

for x in nums:

for j from target down to x:

dp[j] |= dp[j-x]

Verify: