How do you approach Partition Equal Subset Sum?

If the total sum is odd, partitioning into equal halves is impossible.

What is the time complexity of Partition Equal Subset Sum?

Time complexity: O(n * sum) where sum is totalSum / 2. Space complexity: O(sum).

What are common mistakes on Partition Equal Subset Sum?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Partition Equal Subset Sum

MediumAlgorithms

Description

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.

Example 1

Input: nums = [1,5,11,5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2

Input: nums = [1,2,3,5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

Constraints

- 1 <= nums.length <= 200 - 1 <= nums[i] <= 100

Partition Equal Subset Sum: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 8 test cases (5 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

If you are stuck

Show the 3-step hint ladder

If the total sum is odd, partitioning into equal halves is impossible.
This reduces to a subset sum problem: can we find a subset that sums to totalSum / 2?
Use a boolean DP array where dp[j] means we can form sum j from the elements.

The optimal approach

Show the approach: Dynamic Programming (0/1 Knapsack)

If total sum is odd, return false. Otherwise, find if a subset sums to totalSum / 2. Use a 1D DP array where dp[j] indicates whether sum j is achievable. Iterate through nums, updating the DP array from right to left.

Time: O(n * sum) where sum is totalSum / 2
Space: O(sum)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.