Equal Subset Sum Partition

The equal-subset-sum-partition problem asks whether a set of positive integers can be split into two groups whose sums are identical; because the total sum S is fixed, this is really a disguised question of whether some subset sums to exactly S/2 — turning a partition problem into the classic 0/1 subset-sum decision problem, solved by deciding, item by item, which attainable sums remain reachable.

Recognize the pattern

• You are asked for a yes/no (or count) on splitting a set/array into two parts under a sum constraint.
• Each element can be used at most once (0/1, not unbounded) — that rules out coin-change-style unbounded knapsack.
• The total sum is small-to-moderate and known up front, so a target like S/2 can be computed before searching.
• Odd total sum is an instant "False" — no need to search at all.

Brute force → optimal

Brute force: try every subset (2^n possibilities), sum each, check if any equals S/2. Correct but exponential — for n=200 (the stated constraint) this is astronomically infeasible.

Optimal (0/1 knapsack DP): build a boolean table dp[i][s] = "can the first i numbers form sum s?", where s only ever ranges over 0..target (sums above the target are never tracked — they're irrelevant to the yes/no question). Transition: dp[i][s] = dp[i-1][s] OR (s >= num[i-1] AND dp[i-1][s-num[i-1]]) — either skip the i-th number, or take it and check whether the remainder was reachable without it. Base case: dp[i][0] = true for all i (empty subset sums to 0). Answer = dp[n][S/2].

Complexity, derived

The table has (n+1) rows and (S/2+1) columns, and each cell is computed in O(1) from two already-known cells — so total work equals the cell count:

Time  = O(n * S/2) = O(n*S)   -- pseudo-polynomial (depends on VALUE of S, not just n)
Space = O(n * S) for the full table, or O(S) if you roll the table
        to one row and iterate sums DESCENDING (so a cell isn't
        reused within the same item's update).

With n≤200 and num[i]≤100, S≤20000, so n*S ≤ 4,000,000 — comfortably fast, even though it looks exponential-adjacent on paper.

Worked example

Array = {1, 5, 11, 5}. Total sum S = 22, even, so target = 11. Rolling 1-D dp array has size target + 1 = 12, valid indices 0..11 — the same bound used by the reference Java code below, so every sum in this trace stays inside that range. dp[0]=true initially, all else false. Process sums DESCENDING per item so each item is used at most once.

dp[11] is true (first via subset {11}, also via {5, 5, 1}), so the array partitions into two subsets each summing to 11 — e.g. {11} and {1, 5, 5}. Answer: True.

Pitfalls

• Scanning sums ascending in the 1-D rolling array lets one item be used multiple times within the same item's pass (turns 0/1 knapsack into unbounded knapsack) — always scan target → item value, descending.
• Forgetting the odd-sum short-circuit wastes a full DP pass on an instantly-impossible input.
• Off-by-one on array size: the dp array needs indices 0..target inclusive, i.e. size target+1 — never larger, since sums above target are never useful.
• Confusing this with "count the number of subsets" (a related but distinct DP that sums counts, not ORs booleans).

When to use / when NOT — trade-offs

Use this DP when the target/sum range is small enough that O(n·S) is tractable (as bounded here: n≤200, S≤20000). It is simple, robust, and easy to verify.

Named alternative — meet-in-the-middle: split the array in half, enumerate all 2^(n/2) subset sums per half, sort one half and binary-search/two-pointer against the other for a match to S/2. Runs in O(2^(n/2) · n) time and O(2^(n/2)) space — better than the DP when S is huge (values up to 10^9) but n is small (≤40), the opposite regime from this problem's constraints.

Named alternative — bitset trick: represent the dp row as a single big-integer/bitset and do bits |= bits << v per item; this keeps the same O(n·S) asymptotic work but with a much smaller constant (word-level parallelism), useful when S is large and n is small-to-moderate.

Don't reach for full brute force or recursion-without-memoization outside of teaching contexts — it's correct but exponential and will not pass any real constraint.

Takeaways

• Partition-into-two-equal-halves reduces to subset-sum with target = totalSum/2; odd totals are immediately False.
• The DP is 0/1 knapsack in disguise: iterate items outer, sums inner-descending, to enforce "use each item once."
• Every sum tracked stays within 0..target — the dp array size is exactly target+1, never unbounded.
• Complexity is pseudo-polynomial — O(n·S) — fast only because S is bounded by the problem's constraints, not because the algorithm is inherently polynomial in input size.
• Space can be compressed from a 2-D table to a single rolling 1-D array of size S+1.

Recall: why must the inner sum loop iterate in descending order when using a single 1-D dp array, and what bug appears if you iterate ascending instead?

Reference implementation (Java)

class Solution {
    public boolean canPartition(int[] num) {
        int sum = 0;
        for (int n : num) sum += n;
        if (sum % 2 != 0) return false; // can't split an odd sum evenly
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1]; // indices 0..target only
        dp[0] = true; // empty subset sums to 0
        for (int v : num) {
            for (int s = target; s >= v; s--) { // descending: use v at most once
                dp[s] = dp[s] || dp[s - v];
            }
        }
        return dp[target];
    }
}

Source: adapted from the classic 0/1-Knapsack-family "Equal Subset Sum Partition" formulation; complexity, worked trace, and trade-off analysis derived first-principles for this guide.