Skip to content

140 — Partition Equal Subset Sum

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

140 — Partition Equal Subset Sum

LeetCode 416 · Medium. 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.

🍽️ Intuition

Splitting nums into two equal-sum halves is really just one question in disguise: can some subset of nums add up to exactly half the total sum? If such a subset exists, everything left over automatically sums to the other half, so the problem collapses from "find a balanced split" down to "is target = total / 2 reachable by picking some subset of the numbers?" That's a reachability question — walk through the numbers one at a time, and track every sum value that becomes achievable as each number gets considered for inclusion or exclusion.

🚩 Pattern-Recognition Cue

"Can this array be split into two subsets with equal sum" is the subset-sum tell: first collapse it to "is total / 2 a reachable sum using some subset of the elements?" — a boolean reachability question over a 1-D array of achievable totals, where each number either gets folded into the reachable set or doesn't. Any odd total sum is an instant false, since it can never split into two equal integer halves.

🐢 Brute Force

Recurse over every element, trying both "include it in the target subset" and "exclude it," with no memoization — the same remaining targets get reached (and re-explored) via many different subsets.

func canPartitionBruteForce(_ nums: [Int]) -> Bool {
    let total = nums.reduce(0, +)
    guard total % 2 == 0 else { return false }
    let target = total / 2
    let n = nums.count

    func canReach(_ i: Int, _ remaining: Int) -> Bool {
        if remaining == 0 { return true }
        if i >= n || remaining < 0 { return false }
        return canReach(i + 1, remaining - nums[i]) || canReach(i + 1, remaining)
    }

    return canReach(0, target)
}

// smoke test
print(canPartitionBruteForce([1, 5, 11, 5]))   // true  ([1, 5, 5] and [11])
print(canPartitionBruteForce([1, 2, 3, 5]))    // false (total is 11, odd)
print(canPartitionBruteForce([1, 2, 5]))       // false (total is 8, but no subset sums to 4)

Big-O: O(2^n) time — every element branches into "include" and "exclude," and overlapping remaining-target values get re-explored from many different subsets. O(n) space for the recursion stack.

🚀 Optimal

Tabulate every reachable sum from 0 up to target using a boolean array, folding each number in by scanning sums downward so no number gets used more than once per subset.

func canPartition(_ nums: [Int]) -> Bool {
    let total = nums.reduce(0, +)
    guard total % 2 == 0 else { return false }
    let target = total / 2

    var dp = Array(repeating: false, count: target + 1)
    dp[0] = true   // a sum of 0 is always reachable (pick nothing)

    for num in nums where num <= target {
        for i in stride(from: target, through: num, by: -1) {
            if dp[i - num] {
                dp[i] = true
            }
        }
    }

    return dp[target]
}

// smoke test — same cases as the brute force
print(canPartition([1, 5, 11, 5]))   // true
print(canPartition([1, 2, 3, 5]))    // false
print(canPartition([1, 2, 5]))       // false

Big-O: O(n · target) time — for each of the n numbers, scan up to target reachable sums. O(target) space for the dp array.

🔑 The Key Insight

Both versions ask the same question at every element — "does including this number, on top of what's already reachable, unlock a new reachable sum?" — but the brute force re-derives reachability for every remaining target independently at every branch, so the same target values get re-checked across an exponential number of include/exclude paths. The optimal version tabulates all reachable sums at once in a single boolean array, so dp[i - num] being true is a fact computed once and reused instantly rather than re-derived recursively. Scanning i from target down to num (instead of upward) is what keeps each number from being folded into the same subset twice within a single pass — it guarantees dp[i - num] still reflects the state before num was considered this round.

🔗 Related Chapters

  • 1D Dynamic Programming — a boolean reachability array is the decision-problem cousin of Coin Change's counting array: both fold one element/coin at a time into a 1-D table indexed by a running total.
  • Arrays and Strings — dp is a single array scanned in a specific direction (downward) on each pass, the same array-manipulation discipline every 1-D DP problem in this batch depends on for correctness.

🧸 Memory Sentence

Partition Equal Subset Sum is subset-sum reachability wearing a partition costume — it's really just "can some subset hit exactly half the total," tracked one boolean reachable-sum array cell at a time, filled downward so each number is used at most once per pass.

✅ Check Your Understanding

  1. Why does the inner loop go stride(from: target, through: num, by: -1) (scanning downward) instead of scanning upward from num to target? What would break if it scanned upward?
  2. Trace dp through canPartition([1, 5, 11, 5]) after folding in each of the four numbers. At what point does dp[11] first become true?
  3. Why is total % 2 == 0 checked before attempting any DP work, rather than just letting the DP run and returning dp[target] (which would be computed against a fractional or truncated target otherwise)?

⬅️ Previous: Longest Increasing Subsequence · Next: Unique Paths ➡️

Clone this wiki locally