Partition Equal Subset Sum

01-21-2026

Problem Statement

Given a list of integers nums, return True if you can partition the array into two subsets where the sum is equal. Return False if not.

Solution

At first glance, this seems like a pretty easy problem. Maybe we can look for complements in the array and have two batches of complements that sum up to 0. But how could we do this? If I select one number, how does that effect future numbers I can choose? Eventually, this would boil down to enumerating every opportunity of subsets until you either found an answer or reached the end of the search space.

Clearly then, this must be DP. In particular, this is an 0/1 Knapsack problem as we see a few key characteristics:

  1. This is DP
  2. The constraint on the knapsack is that the sum must be: sum(nums) // 2
  3. We have distinct "items" as numbers in the array
  4. They all must either be included in the knapsack or not.

So now that the hard part is figured out, we can go ahead and implement basic knapsack, as there are not really any other nuances to this problem. Let dp[i] represent a True or False value designating with i can be reached with some combination of values in nums. We need to find the true value of dp[target] where target is half of the sum nums. This is simple:

python
total = sum(nums)

if total % 2:
	return False

target = total // 2

if max(nums) > target:
	return False

dp = [False] * (target + 1)
dp[0] = True

for v in nums:
	for i in range(target, v - 1, -1):
		if dp[i - v]:
			dp[i] = True

return dp[target]
  • Runtime Complexity: O(n)
  • Space Complexity: O(n)