Partition Equal Subset Sum

MEDIUM✓ CHIP-TIMEDLC #416 — FULL STATEMENT ↗

The drill: Decide whether an array of positive numbers can be split into two groups with equal totals — every number lands on exactly one side, nothing left out, nothing shared.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of positive numbers arrives, and the question is whether it can be divided into two groups whose totals come out exactly equal. Every number has to land in one group or the other — nothing gets left out, and nothing gets shared between the two.

The groups don't need to be the same size, and there's no requirement about which numbers end up where beyond the totals matching. An odd total rules out any split before a single number is even considered.

The answer is a simple yes or no — whether such a balanced split exists at all, not what the split looks like.

EX 01

nums = [2, 3, 7, 8, 10]

→ true

7 + 8 HITS THE HALF-SUM OF 15

EX 02

nums = [2, 3, 4, 6]

→ false

ODD TOTAL, NO SPLIT CAN EVER BALANCE

EX 03

nums = [4, 4, 4, 4]

→ true

ANY TWO OF THE FOUR MATCH THE OTHER TWO

all values are positive
arrays run up to a couple hundred elements
individual values stay small enough that half the total is a workable target
the answer is true/false only, no split needs to be shown

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

The instant the total is odd, no split can ever balance — rule that out first. Otherwise each side must hit exactly half the sum, so the real question becomes: can some subset reach target = sum ÷ 2?

HINT 2 THE STRUCTURE

Every number faces a binary choice — join the target subset, or don't. That's a decision tree with 2ⁿ leaves, and a lot of those branches chase totals that were already reached another way.

HINT 3 ONE STEP FROM THE ANSWER

Track reachability instead of choices: which totals up to target are buildable using the numbers seen so far? A boolean array updated backward per number turns the search into O(n·target) instead of 2ⁿ.

COACH'S BOARD — THE PATTERN, STEP BY STEP

REACHABLE HALF-SUMPATTERN · SUBSET-SUM DPnums = [4, 4, 4, 4] · target = 8

STEP 1

Total is 16, so the target is half-sum 8. Sum 0 starts reachable — taking nothing always works.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/partition-equal-subset-sum.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        reachable = [False] * (target + 1)
        reachable[0] = True
        for x in nums:
            for s in range(target, x - 1, -1):  # right-to-left: each number used once
                if reachable[s - x]:
                    reachable[s] = True
        return reachable[target]

TIME O(N·SUM)SPACE O(SUM)PYTHON · RACE PACE · 13 LN

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        n = len(nums)

        def backtrack(i: int, remaining: int) -> bool:
            if remaining == 0:
                return True
            if i == n or remaining < 0:
                return False
            # this number joins the target subset, or it doesn't
            return backtrack(i + 1, remaining - nums[i]) or backtrack(i + 1, remaining)

        return backtrack(0, target)

TIME O(2ⁿ)SPACE O(N)PYTHON · TRAINING PACE · 17 LN

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) {
            total += x;
        }
        if (total % 2 != 0) {
            return false;
        }
        int target = total / 2;
        boolean[] reachable = new boolean[target + 1];
        reachable[0] = true;
        for (int x : nums) {
            for (int s = target; s >= x; s--) {
                if (reachable[s - x]) {
                    reachable[s] = true;
                }
            }
        }
        return reachable[target];
    }
}

TIME O(N·SUM)SPACE O(SUM)JAVA · RACE PACE · 22 LN

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) {
            total += x;
        }
        if (total % 2 != 0) {
            return false;
        }
        return backtrack(nums, 0, total / 2);
    }

    private boolean backtrack(int[] nums, int i, int remaining) {
        if (remaining == 0) {
            return true;
        }
        if (i == nums.length || remaining < 0) {
            return false;
        }
        return backtrack(nums, i + 1, remaining - nums[i]) || backtrack(nums, i + 1, remaining);
    }
}

TIME O(2ⁿ)SPACE O(N)JAVA · TRAINING PACE · 22 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED