Partition Equal Subset Sum: 0/1 Knapsack in Disguise

"Partition Equal Subset Sum" shows up again and again in Meta, Amazon, Uber phone screens. It is a Medium problem on paper, but the real test is whether you recognize the Dynamic Programming pattern quickly and code it cleanly. Part 10 of 11 in the Dynamic Programming arc.

The Problem

Can an array of positive integers be partitioned into two subsets with equal sums? Reduces immediately: odd total means no; otherwise, does any subset hit half the total? That is subset-sum — 0/1 knapsack's decision form — and the backward iteration is where candidates get cut.

Input:  nums = [1, 5, 11, 5]
Output: True
[1, 5, 5] and [11].

Recognizing the Dynamic Programming Pattern

Dynamic programming is recursion with the repetition removed: define the answer to a subproblem, express it in terms of smaller subproblems, and compute each exactly once — top-down with memoization or bottom-up with a table. In interviews the grade hinges on the state definition said out loud ('dp[i] is the best answer using the first i items') far more than on the loop that follows. Most FAANG DP questions are one-dimensional or a small 2D grid — the nine below cover the shapes that repeat.

Each element used at most once toward a target sum: 0/1 knapsack. The 1D compression keeps dp[t] — is sum t achievable — but requires iterating targets downward, so this round's placement of an item cannot feed on itself. Forward iteration silently answers the unbounded (coin-style) question instead.

The Approach

Boolean array over 0..half, dp[0] seeded True. Per number, sweep targets from high to low: dp[t] |= dp[t − num]. Early-exit when dp[half] turns True.

Be ready to explain the loop direction with a concrete failure: nums = [5], target 10 — forward iteration marks 5 then reuses it to mark 10, using one element twice. The direction is the question; everything else is bookkeeping. A bitset (Python int shifts) does the whole table in a few machine words — a genuine wow-move if time allows.

Python Solution

def can_partition(nums: list[int]) -> bool:
    """True if nums splits into two equal-sum subsets."""
    total = sum(nums)
    if total % 2:
        return False
    half = total // 2
    dp = [True] + [False] * half
    for num in nums:
        for t in range(half, num - 1, -1):    # backward: 0/1 semantics
            if dp[t - num]:
                dp[t] = True
        if dp[half]:
            return True
    return dp[half]

Complexity

• Time: O(n·S) — n items times the half-sum range S — pseudo-polynomial
• Space: O(S) — one boolean row

Interview Tips and Follow-Ups

• Say 'pseudo-polynomial' and mean it: the cost scales with the value of the sum, not the input length — subset-sum is NP-complete in the strong sense.
• The bitset formulation (bits |= bits << num, check bit half) is the same DP at word-level speed — Python ints make it three lines.
• Target Sum (assign plus and minus signs) reduces to this exact subset-sum — one algebraic step; a very common Meta chain.

If this clicked, continue the Dynamic Programming arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.