Partition Equal Subset Sum

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Given an array of positive integers, decide whether it can be split into two groups with equal sums. Every number goes into exactly one group. The same question is often asked in its general form: is there a subset whose sum is exactly target? Partition is that question with target = sum / 2.

    The friendliest introduction to 0/1 knapsack. It tests whether you can turn "try every subset" into a table of reachable sums, and whether you know the loop-direction detail that keeps each item from being used twice. Original problem: LeetCode 416.

    Example

    The total is 24, so each group needs 12: {7, 5} and {4, 2, 6}. For [2, 3, 7] the total is 12 but no subset makes 6.
    The total is 24, so each group needs 12: {7, 5} and {4, 2, 6}. For [2, 3, 7] the total is 12 but no subset makes 6.
    Input:  [4, 7, 2, 5, 6]
    Output: true        # {7, 5} and {4, 2, 6}, both 12
    Input:  [2, 3, 7]
    Output: false       # total 12, but no subset sums to 6
    Input:  [1, 2, 4]
    Output: false       # odd total: impossible

    Constraints (assumed)

    • 1 ≤ n ≤ 200; 1 ≤ nums[i] ≤ 100, so the total is at most 20,000.
    • All numbers are positive.

    What this question tests

    • Reducing partition to subset sum (target = total / 2, and odd totals are impossible).
    • A reachable-sums DP with the right loop direction for 0/1 items.
    • Knowing the complexity is pseudo-polynomial: it depends on the size of the numbers, not just on n.

    Questions to ask first

    1. Are all numbers positive? Negative numbers break the bounded table. (Here: positive.)
    2. How large can the numbers and their total be? The DP is O(n · total).
    3. Two groups, or k groups? Partition into k equal groups is much harder (backtracking or bitmask DP).
    4. Just yes/no, or the actual split? (Here: yes/no; the split is a follow-up.)