Partition Equal Subset Sum: 0/1 Knapsack in Disguise

Given a non-empty array of positive integers, can you split it into two subsets where both subsets have the same sum?

This is LeetCode 416: Partition Equal Subset Sum, and it looks like a partitioning problem on the surface. But the real trick is recognizing that it is actually a 0/1 knapsack problem in disguise. Once you see the reduction, the solution practically writes itself.

The key insight: reducing to knapsack

Here is the thought process. If you split an array into two subsets with equal sums, each subset must sum to exactly half the total. So the question becomes: can you find a subset of the array that sums to total / 2?

That is a classic 0/1 knapsack question. Each element is an "item" you either take or skip. The "knapsack capacity" is total / 2. You are not optimizing for value here, just asking a yes/no question: is the target sum reachable?

A few things fall out of this immediately:

• If the total sum is odd, return False right away. You cannot split an odd number into two equal integers.
• If any single element is bigger than total / 2, return False. That element cannot belong to either subset without exceeding the target.
• Otherwise, build a DP table to check whether sum total / 2 is achievable.

This reduction is the entire problem. The DP itself is straightforward once you frame it correctly.

Starting with recursion

For each element, you have two choices: include it in the subset or skip it. If you include it, subtract its value from the remaining target. If you skip it, move on to the next element with the same target.

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

    target = total // 2

    def helper(i, remaining):
        if remaining == 0:
            return True
        if i >= len(nums) or remaining < 0:
            return False

        # Take or skip
        return helper(i + 1, remaining - nums[i]) or helper(i + 1, remaining)

    return helper(0, target)

This is correct but exponential. Each element branches into two choices, giving O(2^n) time. For an array of 200 elements (the LeetCode constraint), that is not going to work.

Adding memoization (top-down DP)

The recursive solution recomputes the same (index, remaining) pairs over and over. Cache them.

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

    target = total // 2
    memo = {}

    def helper(i, remaining):
        if remaining == 0:
            return True
        if i >= len(nums) or remaining < 0:
            return False
        if (i, remaining) in memo:
            return memo[(i, remaining)]

        memo[(i, remaining)] = (
            helper(i + 1, remaining - nums[i]) or
            helper(i + 1, remaining)
        )
        return memo[(i, remaining)]

    return helper(0, target)

Now each (i, remaining) pair is solved at most once. There are n possible values for i and target possible values for remaining, so time is O(n * target) and space is O(n * target) for the memo table. Much better.

Building the DP table (bottom-up)

The bottom-up version uses a 1D boolean array. dp[j] answers the question: "can we form sum j using some subset of the elements processed so far?"

The algorithm:

1. Start with dp[0] = True (sum 0 is always achievable with the empty subset).
2. For each number num in the array, iterate j from target down to num. If dp[j - num] is True, then dp[j] becomes True too.
3. After processing all numbers, check dp[target].

Why iterate backwards? Because each element can only be used once (this is 0/1 knapsack, not unbounded). If you iterated forwards, you could accidentally use the same element multiple times in a single pass. Going from right to left ensures that when you read dp[j - num], it reflects the state before including the current element.

Let's trace through nums = [1, 5, 11, 5], where total = 22 and target = 11:

The moment dp[11] flips to True, we know a valid partition exists. We do not even need to know which elements are in which subset. The boolean answer is enough.

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

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

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

    return dp[target]

Time: O(n * target) where n is the length of the array and target is total / 2.

Space: O(target). A single boolean array.

That backward inner loop is the only subtle part. Everything else is standard DP boilerplate.

Why 0/1 knapsack and not unbounded?

In Coin Change, you can use each denomination as many times as you want. That makes it unbounded knapsack. Here, each array element belongs to exactly one subset. You cannot put the same element in both. That is the 0/1 constraint: each item is either "in" (taken) or "out" (skipped), exactly once.

The structural difference in code is small but critical:

• Unbounded (Coin Change): inner loop goes from coin to target (left to right). Updated cells can be used again in the same pass, allowing reuse.
• 0/1 (Partition Equal Subset Sum): inner loop goes from target down to num (right to left). Each cell is only updated using values from the previous pass, preventing reuse.

If you accidentally iterate forward in this problem, you will get wrong answers because the same number gets "used" multiple times.

Complexity analysis

Where target = sum(nums) / 2. For LeetCode constraints (n up to 200, values up to 100), target can be at most 10,000. So the DP table has at most 10,001 entries and you loop through it at most 200 times. That is 2 million operations, which runs in milliseconds.

Edge cases to watch for

• Odd total: return False immediately. No need to build any DP table.
• Single element: an array with one number cannot be split. Return False.
• Element equals target: e.g., nums = [3, 3]. The first element makes dp[3] True, and you are done.
• All identical elements: e.g., [4, 4, 4, 4]. Total is 16, target is 8. Works fine: pick any two elements.
• Large single element exceeding target: e.g., nums = [1, 2, 5], total = 8, target = 4. Element 5 exceeds the target on its own, but the DP naturally handles this because the inner loop starts at target and only goes down to num.

The building blocks

This problem is built on take-or-skip DP, the same core decision pattern as House Robber. At every element, you decide: include this number in the target subset, or leave it out? The DP records the consequences of all possible combinations of those decisions.

The structure:

• State: dp[j] = can we achieve sum j using elements seen so far?
• Transition: for each num, set dp[j] = True if dp[j - num] was already True
• Loop direction: backward (right to left) to enforce the 0/1 constraint

This same building block appears in many other problems:

• Target Sum (LeetCode 494): same partition idea with a twist. Reduce to "find a subset that sums to (total + target) / 2."
• Last Stone Weight II (LeetCode 1049): minimize the remaining stone weight. Reduces to finding a subset sum as close to total / 2 as possible. Same DP.
• 0/1 Knapsack (classic): the textbook version with weights and values. Same take-or-skip structure, but you track max value instead of reachability.

Once you recognize the 0/1 knapsack skeleton, these problems are all the same DP with different wrappers.

From understanding to recall

The reduction from "partition into equal subsets" to "find a subset summing to half" is the kind of insight that feels obvious once you see it, but is easy to blank on during an interview. Spaced repetition helps lock in these reductions so they fire automatically when you see a new problem.

The take-or-skip DP building block is one of roughly 60 reusable patterns that cover hundreds of LeetCode problems. Drilling the 0/1 knapsack pattern individually, writing the backward loop from scratch each time, and spacing your reps out over days and weeks is how you get from "I understand it" to "I can write it cold."

Related posts

• Coin Change - Unbounded knapsack DP, where the inner loop goes forward instead of backward. Great contrast with this problem.
• House Robber - The same take-or-skip decision at each element, applied to a linear optimization problem instead of a subset reachability problem.