Partition Equal Subset Sum — 0/1 Knapsack on a Boolean Array

Problem Statement#

Given a non-empty array nums of positive integers, determine whether the array can be partitioned into two subsets such that both subsets have equal sums.

Example: nums = [1, 5, 11, 5] returns true. We can split into [1, 5, 5] and [11], each summing to 11.

Example: nums = [1, 2, 3, 5] returns false. The total is 11, which is odd, so no equal split exists.

Constraints: 1 is less than or equal to nums.length is less than or equal to 200, and 1 is less than or equal to nums[i] is less than or equal to 100. So the maximum total sum is 20000 and the target is at most 10000 — perfect for a pseudo-polynomial DP.

Why This Problem Matters#

Partition Equal Subset Sum is the cleanest gateway to the 0/1 knapsack pattern that dominates dynamic programming interviews at Amazon, Microsoft, Meta, and most quant shops. It teaches three things at once: how to reduce a problem to a known DP shape, why the iteration order matters when you collapse a 2D table to 1D, and how to spot pseudo-polynomial complexity dependent on the input values rather than the input length.

Once you internalize this recurrence, Target Sum, Last Stone Weight II, Ones and Zeroes, and even Coin Change variants become easy adaptations of the same template.

The Core Insight (Recurrence)#

If the total sum S is odd, no equal split exists — return false immediately. Otherwise the question becomes: can a subset of nums sum to exactly target = S / 2?

Define dp[j] as a boolean: "Can we form sum j using some subset of the elements processed so far?" The base case is dp[0] = true because the empty subset always sums to 0.

For each number n, transition: dp[j] = dp[j] OR dp[j - n]. Either we skip n (left side keeps its value) or we include n once and the new reachable sum is j (which depends on the previously reachable j - n).

The 2D version dp[i][j] says "using the first i items, can we reach sum j." The 1D collapse is correct only if we iterate j from target down to n. Iterating left-to-right would let the same item be picked multiple times (turning this into the unbounded knapsack), which violates the 0/1 constraint.

Building the DP Solution (Recursion to Memo to Tabulation)#

Top-down: canReach(i, j) returns true if some subset of nums[i..] sums to j. Recurse into canReach(i + 1, j) (skip) or canReach(i + 1, j - nums[i]) (take). Memoize on (i, j).

Tabulation 2D: allocate dp[n + 1][target + 1] and fill row by row.

Tabulation 1D: keep a single boolean array of length target + 1. For each n in nums, loop j from target down to n and update dp[j] |= dp[j - n]. The reverse iteration ensures each item is used at most once.

Bitset trick (Python or C++): represent dp as one big integer where bit j is 1 iff sum j is reachable. Each item update becomes dp |= dp << n, which is O(target / word_size) per number — usually 32x or 64x faster in practice.

Visual Dry Run (DP Table Trace)#

Trace nums = [1, 5, 11, 5]. Total is 22, target is 11. Initialize dp = [T, F, F, F, F, F, F, F, F, F, F, F] where index 0..11.

Process n = 1 (loop j = 11 down to 1):

• dp[1] |= dp[0] -> dp[1] = T.
• All other reverse updates are F. After: indices reachable are {0, 1}.

Process n = 5 (j = 11 down to 5):

• dp[6] |= dp[1] -> T.
• dp[5] |= dp[0] -> T.
• After: {0, 1, 5, 6}.

Process n = 11 (j = 11 down to 11):

• dp[11] |= dp[0] -> T.
• After: {0, 1, 5, 6, 11}.

dp[11] is already true so we could short-circuit. Process n = 5 (j = 11 down to 5):

• dp[11] |= dp[6] -> still T.
• dp[10] |= dp[5] -> T.
• And so on. After: {0, 1, 5, 6, 10, 11}.

dp[target] = dp[11] = true. Return true. The witness subset is {11}.

Optimized Solution — Space-Optimized Python and JavaScript#

Python — Bitset One-Liner#

from typing import List
 
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        bits = 1  # bit 0 set means sum 0 reachable.
        for n in nums:
            bits |= bits << n
        return (bits >> target) & 1 == 1

Python — Boolean DP#

from typing import List
 
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True
        for n in nums:
            for j in range(target, n - 1, -1):
                dp[j] = dp[j] or dp[j - n]
            if dp[target]:
                return True
        return dp[target]

JavaScript#

var canPartition = function (nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2) return false;
  const target = total / 2;
  const dp = new Uint8Array(target + 1);
  dp[0] = 1;
  for (const n of nums) {
    for (let j = target; j >= n; j -= 1) {
      if (dp[j - n]) dp[j] = 1;
    }
    if (dp[target]) return true;
  }
  return dp[target] === 1;
};

Complexity Analysis#

• Time: O(n * target) where target is sum / 2. For LeetCode constraints that is at most 200 * 10000 = 2 * 10^6 — comfortably fast.
• Space: O(target) for the boolean array, or O(target / word_size) for the bitset variant.
• The complexity is pseudo-polynomial because it depends on the magnitude of the values, not just the count. If values could be up to 10^9, this DP is no longer feasible.

Common Mistakes#

• Iterating j left to right. That allows the same number to be picked multiple times and turns the answer into unbounded knapsack. Always go right to left for 0/1 knapsack.
• Skipping the parity check. If total is odd, return false immediately — otherwise you allocate a wasted DP array.
• Using dp[j] = dp[j - n]. That overwrites previously achievable sums. Use dp[j] = dp[j] OR dp[j - n].
• Allocating target + 1 instead of target. Off-by-one is the second-most-common bug; remember dp[0] is reachable.
• Confusing this with Coin Change. Coin Change is unbounded; partition is 0/1.

Interview Tips#

• Open with the reduction: "Equal partition exists iff some subset sums to total/2." That single sentence demonstrates problem-translation skill.
• Walk the iteration order out loud. Saying "I iterate j from target down to n to keep this 0/1" is what separates strong DP candidates.
• If asked for the partition itself, reconstruct by walking the 2D table backwards and tracking which items were taken.
• Mention the bitset speedup as a follow-up — many shops appreciate the practical engineering insight.

Follow-up Questions#

• Return the actual subsets, not just a boolean. Hint: keep a 2D table to reconstruct.
• Last Stone Weight II — minimize the difference between the two subset sums. Same DP, different objective.
• Count the number of subsets with target sum (LeetCode 494 Target Sum). The boolean turns into an integer count.
• Partition into k subsets of equal sum (LeetCode 698). That is bitmask DP, not knapsack.

Key Takeaways#

• Partition Equal Subset Sum reduces cleanly to "subset sums to total/2" — a textbook 0/1 knapsack instance.
• The 1D DP collapse requires iterating j from target down to n to preserve the 0/1 property.
• Time complexity is pseudo-polynomial: O(n * sum/2). Always check whether the value range allows it before committing.
• Boolean tabulation, top-down memoization, and bitset all work; bitset gives a 32x to 64x constant-factor speedup.
• This pattern is the parent of Target Sum, Last Stone Weight II, Ones and Zeroes, and many other knapsack-shaped problems.
• When in doubt, recite: "0/1 means iterate amounts backward; unbounded means iterate forward."