On this page
Description
Sometimes the question isn't "what's the best subset?" but "does any subset add up to exactly this sum?" Can these payments exactly cover an invoice? Can these items be split into two equal halves? With n numbers there are 2^n subsets, but only target + 1 sums matter, so a boolean table over sums answers the question. This skill covers that table, the partition check, and how to get an actual subset back.
We'll go from simple to more technical:
- The pattern:
reachable[s], swept downward per number, starting from reachable[0] = true. - A second flavor: splitting into two equal halves (check the parity first).
- Where exact-sum checks show up (reconciliation, load balancing).
- What breaks it: upward sweeps, the empty subset, odd totals, huge sums.
The approach
Java
boolean subsetSumExists(int[] nums, int target) {
boolean[] reachable = new boolean[target + 1];
reachable[0] = true; // the empty subset sums to 0
for (int x : nums) {
for (int s = target; s >= x; s--) { // downward: each number used at most once
if (reachable[s - x]) reachable[s] = true;
}
}
return reachable[target];
}
Python
def subset_sum_exists(nums: list[int], target: int) -> bool:
reachable = [False] * (target + 1)
reachable[0] = True # the empty subset sums to 0
for x in nums:
for s in range(target, x - 1, -1): # downward: each number used at most once
if reachable[s - x]:
reachable[s] = True
return reachable[target]
After processing some numbers, reachable[s] says whether a subset of them sums to s. A new number x makes s reachable if s - x already was. The downward sweep is the 0/1-knapsack rule: reachable[s - x] must reflect the numbers before x, or x could be used twice - sweeping upward, the single number 5 "reaches" 10. Everything starts from reachable[0] = true; without it nothing is ever reachable.
A second flavor: splitting into two equal halves
Partitioning numbers into two subsets with equal sums is subset sum in disguise: each half must sum to total / 2. So check the total first:
Java
int total = 0;
for (int x : nums) total += x;
if (total % 2 != 0) return false; // an odd total can't be halved
return subsetSumExists(nums, total / 2);
Python
def can_partition(nums: list[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False # an odd total can't be halved
return subset_sum_exists(nums, total // 2)
Skipping the parity check is a real bug, not a shortcut: for [1, 2], total / 2 rounds down to 1, which is reachable, so the code would claim a split exists. Replace boolean with a count (ways[s] += ways[s - x]) and the same table counts the subsets instead.
Where you'll see it
Reconciliation (which open invoices add up to this payment?), load balancing across two machines (split jobs so both finish together), and "exact change" checks in payment and gift-card systems are subset-sum questions. In finance reconciliation tools, the reachable-sums table (with parent pointers) also recovers which items match.
Which tool for which job?
| You need | Use |
|---|---|
| Does a subset hit the target? | a boolean table over sums, swept downward |
| Two equal halves | parity check, then subset sum to total / 2 |
| The halves as close as possible | the reachable sum nearest total / 2 |
| The subset itself | a "first reached by" index per sum, walked back |
| A nonempty subset divisible by k, n ≥ k | prefix sums mod k (pigeonhole), O(n) |
| Many repeated small values | group equal values, then binary splitting |
| Huge values, n up to about 40 | meet in the middle |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Sweeping upward | [5] reaches 10 | sweep downward |
reachable[0] left false | nothing is ever reachable | the empty subset sums to 0 |
| No parity check | [1, 2] "splits" because 3 / 2 rounds to 1 | an odd total can't be halved |
| A table for sums near 10^9 | too large | meet in the middle for small n |
| The 1D table when the subset is needed | the choices are overwritten | record which number first reached each sum |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why sweep s from target down to x?
Show answer
So reachable[s - x] still describes subsets of the earlier numbers. Sweeping upward, it may have just been set using x itself, letting x count twice - [5] with target 10 would be "reachable".
2. [1, 2]: can it be split into two equal-sum subsets? What does the code return without the parity check?
Show answer
No - the total 3 is odd. Without the check, total / 2 = 1 is reachable ({1}), so the code wrongly returns true.
3. How does the table change to count subsets instead of checking existence?
Show answer
Store counts: ways[0] = 1 and ways[s] += ways[s - x], still sweeping downward. The recurrence is identical; OR becomes +.
Key takeaways
- reachable[s] = some subset of the numbers so far sums to s; reachable[0] = true.
- For each number, sweep sums downward so it's used at most once.
- Equal partition = subset sum to total / 2 - after checking the total is even.
- Counting subsets is the same table with + instead of OR.
- O(n * target): pseudo-polynomial; huge values need meet-in-the-middle.