Partition Equal Subset Sum
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 withtarget = 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.](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/000-41d590d3-56.png)
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
- Are all numbers positive? Negative numbers break the bounded table. (Here: positive.)
- How large can the numbers and their total be? The DP is O(n · total).
- Two groups, or k groups? Partition into k equal groups is much harder (backtracking or bitmask DP).
- Just yes/no, or the actual split? (Here: yes/no; the split is a follow-up.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.