Partition Equal Subset Sum

Difficulty: Medium Source: NeetCode

Problem

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 ([1,5,5] and [11])

Example 2: Input: nums = [1,2,3,5] Output: false

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• 0/1 Knapsack — each item can be used at most once
• Subset Sum — can a subset of elements sum to a target?
• Boolean DP — tracking reachable sums

1. Brute Force (Recursion)

Intuition

If we can find a subset that sums to exactly total // 2, the remaining elements automatically sum to the same amount. So the problem reduces to: “can we find a subset summing to target = total // 2?” Recursively try including or excluding each element.

Algorithm

1. Compute total = sum(nums). If total is odd, return False immediately.
2. Set target = total // 2.
3. Use recursion: at each index, either include the current element or skip it.
4. Return True if we can reach exactly target.

Solution

def canPartition_brute(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False

    target = total // 2
    memo = {}

    def dp(i, remaining):
        if remaining == 0:
            return True
        if remaining < 0 or i >= len(nums):
            return False
        if (i, remaining) in memo:
            return memo[(i, remaining)]
        # Include nums[i] or skip it
        result = dp(i + 1, remaining - nums[i]) or dp(i + 1, remaining)
        memo[(i, remaining)] = result
        return result

    return dp(0, target)


print(canPartition_brute([1, 5, 11, 5]))  # True
print(canPartition_brute([1, 2, 3, 5]))   # False
print(canPartition_brute([1, 1]))          # True
print(canPartition_brute([1, 2, 5]))       # False

Complexity

• Time: O(n * target) with memoization
• Space: O(n * target) — memo table

2. 0/1 Knapsack DP (Boolean Set)

Intuition

Use a boolean set dp where dp[j] means “we can make sum j from elements seen so far.” Start with dp = {0} (we can always make sum 0). For each number, update the set: every reachable sum j can become j + num if we include the current element.

Process elements one at a time, iterating sums in descending order (or use a new set each round) so we don’t use the same element twice (0/1 knapsack constraint).

Algorithm

1. Check odd total → False.
2. Initialize dp = {0} (achievable sums).
3. For each num in nums:
   • For each j in current dp (iterate backwards if using an array):
     • Add j + num to dp.
   • If target is in dp: return True early.
4. Return target in dp.

Solution

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False

    target = total // 2
    dp = {0}  # achievable sums

    for num in nums:
        new_dp = set()
        for j in dp:
            new_dp.add(j)
            new_dp.add(j + num)
        dp = new_dp
        if target in dp:
            return True

    return target in dp


def canPartition_array(nums):
    """Same idea, but with a boolean array — classic knapsack formulation."""
    total = sum(nums)
    if total % 2 != 0:
        return False

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

    for num in nums:
        # Iterate in reverse to avoid reusing the same element
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]

    return dp[target]


print(canPartition([1, 5, 11, 5]))  # True
print(canPartition([1, 2, 3, 5]))   # False
print(canPartition([1, 1]))          # True

print(canPartition_array([1, 5, 11, 5]))  # True
print(canPartition_array([1, 2, 3, 5]))   # False
print(canPartition_array([3, 3, 3, 4, 5]))  # True

Complexity

• Time: O(n * target) — n elements × target sums
• Space: O(target) — boolean DP array

Common Pitfalls

Not checking if total is odd. If the total sum is odd, it’s impossible to split evenly. Always check this first as an early exit.

Iterating the inner loop forward in the array version. In the dp array approach, you must iterate j from target down to num. Forward iteration would let the same element be used multiple times (turning it into unbounded knapsack).

Using a set but forgetting it’s copied each round. If you iterate over dp while modifying it in the same loop, you’ll include elements multiple times. Either iterate over a copy (for j in dp.copy()) or build a new set each round.