These are the notes for DSA episode 70. Two friends come back from the vegetable market with four bags: 1, 5, 11 and 5 kg. Can they split the bags so both carry exactly the same weight? We spot two facts first (an odd total can never be split; an even total only needs one group of total / 2), write the obvious "take this bag or skip it" recursion (correct, then Time Limit Exceeded on 41 bags), draw the key insight as a table, can[i][s] = can[i-1][s] OR can[i-1][s - w], type it live, print the two groups, and shrink it to one row with the loop running down, the same trick as the 0/1 knapsack in episode 65. Then three real bugs. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).
The problem, in real life
| Coming back from the market | In code |
|---|---|
| The bags: 1, 5, 11, 5 kg | the array nums |
| Every bag must be carried by someone | every number goes into exactly one group |
| Both friends carry the same weight | the two groups have equal sums |
| Total 22 kg, so 11 kg each | target = total / 2 |
| Friend A's bags | a subset that sums to total / 2 |
| Friend B carries the rest | the complement, automatically total / 2 |
| Bags 1, 2, 3, 5 (11 kg, odd) | impossible: false straight away |
Every word, from zero
- Subset: any choice of some of the items (possibly none, possibly all), each item at most once.
[1, 5, 5]is a subset of[1, 5, 11, 5]. - Partition: splitting all the items into groups so that every item is in exactly one group.
- Subset sum: the question "is there a subset whose numbers add up to exactly
T?". - Complement: the items not in the chosen subset. If the subset sums to
total / 2, the complement sums tototal - total / 2 = total / 2. - Parity: whether a number is even or odd. Two equal whole numbers always add up to an even number.
- State: the few numbers that fully describe a sub-problem; here
(i, s): the firstibags, and a weights. - Recurrence: the rule for a state from smaller states: skip OR take.
- Base case:
can[0][0] = true(no bags make 0 kg) andcan[0][s] = falsefors > 0. - Tabulation (bottom-up): filling the table row by row so every cell we read is already done.
- Rolling array / one row: keeping only one row of the table.
- 0/1 knapsack: each item can be taken 0 or 1 times; the one-row loop must run down so an item is not reused.
- Pseudo-polynomial: fast because a number in the input (the sum) is small, not because the input is short.
- Bitset: a row of bits; bit
sset means "skg is reachable".
Problem statement
Partition Equal Subset Sum (LeetCode 416). Given an array of positive integers nums, return true if it can be split into two subsets with equal sums. 1 ≤ n ≤ 200, 1 ≤ nums[i] ≤ 100, so the total is at most 20,000 and total / 2 at most 10,000.
| nums | Answer | Why |
|---|---|---|
[1, 5, 11, 5] |
true |
[11] and [1, 5, 5] |
[1, 2, 3, 5] |
false |
the total, 11, is odd |
[1] |
false |
one bag can't be split |
[2, 2] |
true |
one bag each |
[2, 2, 3, 5] |
false |
the total is 12, but no subset makes 6 |
First insight: find just one group
- Odd total → false. Two equal whole numbers add up to an even number.
- Even total → find one subset with sum
total / 2. The leftover items automatically make the other half.
So the problem becomes subset sum with target half = total / 2.
Obvious idea: take it or skip it
can(i, need): can bags i, i+1, ... make exactly need kg? Either bag i is taken (need - w[i]) or skipped.
import java.util.*;
public class Main {
static boolean canPartition(int[] w) {
int total = 0;
for (int x : w) total += x;
if (total % 2 == 1) return false;
return can(w, 0, total / 2);
}
static boolean can(int[] w, int i, int need) {
if (need == 0) return true;
if (i == w.length || need < 0) return false;
return can(w, i + 1, need - w[i]) || can(w, i + 1, need);
}
public static void main(String[] args) {
System.out.println(canPartition(new int[]{1, 5, 11, 5}));
System.out.println(canPartition(new int[]{1, 2, 3, 5}));
System.out.println(canPartition(new int[]{1}));
System.out.println(canPartition(new int[]{2, 2}));
System.out.println(canPartition(new int[]{2, 2, 3, 5}));
}
}
true
false
false
true
false
Correct, now a big trip: forty bags of 2 kg and one of 6 kg. The total is 86, half is 43, and every bag is even, so no subset can make 43. To prove it, the recursion tries subset after subset:
import java.util.*;
public class Main {
static boolean canPartition(int[] w) {
int total = 0;
for (int x : w) total += x;
if (total % 2 == 1) return false;
return can(w, 0, total / 2);
}
static boolean can(int[] w, int i, int need) {
if (need == 0) return true;
if (i == w.length || need < 0) return false;
return can(w, i + 1, need - w[i]) || can(w, i + 1, need);
}
public static void main(String[] args) {
int[] bags = new int[41];
Arrays.fill(bags, 2);
bags[40] = 6;
long t0 = System.nanoTime();
boolean ok = canPartition(bags);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("41 bags: " + ok + ", " + ms + " ms");
}
}
Time Limit Exceeded (stopped after 25 s)
Why is it slow?
- 41 bags have
2^41(over two trillion) subsets. - A call depends only on
(i, need). "Take bag 0, skip bag 1" and "skip bag 0, take bag 1" both lead to(2, 41), and from there the same work is repeated. - There are only
42 × 44different(i, need)pairs here. DP answers each once.
The key insight: skip OR take
| Step | Rule |
|---|---|
| State | can[i][s] = can some of the first i bags make exactly s kg? |
Skip bag i |
can[i - 1][s] |
Take bag i (weight w) |
can[i - 1][s - w], only if s ≥ w |
| Recurrence | can[i][s] = skip OR take |
| Base | can[0][0] = true, can[0][s > 0] = false |
| Answer | can[n][total / 2] |
It is the 0/1 knapsack with booleans: OR instead of max.
By hand: bags 1, 5, 11, 5, target 11
✓ = that weight can be made.
| bags used | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| none | ✓ | · | · | · | · | · | · | · | · | · | · | · |
| + 1 kg | ✓ | ✓ | · | · | · | · | · | · | · | · | · | · |
| + 5 kg | ✓ | ✓ | · | · | · | ✓ | ✓ | · | · | · | · | · |
| + 11 kg | ✓ | ✓ | · | · | · | ✓ | ✓ | · | · | · | · | ✓ |
| + 5 kg | ✓ | ✓ | · | · | · | ✓ | ✓ | · | · | · | ✓ | ✓ |
Each row keeps every tick of the row above (skip) and adds the bag's weight to each tick (take). The bottom right is ✓: true.
Solution in Java: the 2D table
import java.util.*;
public class Main {
static boolean canPartition(int[] w) {
int total = 0;
for (int x : w) total += x;
if (total % 2 == 1) return false;
int half = total / 2, n = w.length;
boolean[][] can = new boolean[n + 1][half + 1];
can[0][0] = true;
for (int i = 1; i <= n; i++)
for (int s = 0; s <= half; s++) {
can[i][s] = can[i - 1][s];
if (s >= w[i - 1] && can[i - 1][s - w[i - 1]]) can[i][s] = true;
}
return can[n][half];
}
public static void main(String[] args) {
System.out.println(canPartition(new int[]{1, 5, 11, 5}));
System.out.println(canPartition(new int[]{1, 2, 3, 5}));
System.out.println(canPartition(new int[]{1}));
System.out.println(canPartition(new int[]{2, 2}));
System.out.println(canPartition(new int[]{2, 2, 3, 5}));
}
}
true
false
false
true
false
Which bags? Walk back
Walk back from can[n][half]: if the row above could already make s, bag i wasn't needed (friend B); otherwise friend A took it and s -= w[i - 1].
import java.util.*;
public class Main {
static void split(int[] w) {
int total = 0;
for (int x : w) total += x;
int half = total / 2, n = w.length;
boolean[][] can = new boolean[n + 1][half + 1];
can[0][0] = true;
for (int i = 1; i <= n; i++)
for (int s = 0; s <= half; s++)
can[i][s] = can[i - 1][s] || (s >= w[i - 1] && can[i - 1][s - w[i - 1]]);
if (total % 2 == 1 || !can[n][half]) { System.out.println("no split"); return; }
List<Integer> a = new ArrayList<>(), b = new ArrayList<>();
int s = half;
for (int i = n; i >= 1; i--) {
if (can[i - 1][s]) b.add(w[i - 1]);
else { a.add(w[i - 1]); s -= w[i - 1]; }
}
System.out.println(a + " and " + b);
}
public static void main(String[] args) {
split(new int[]{1, 5, 11, 5});
split(new int[]{3, 1, 4, 2, 2});
split(new int[]{1, 2, 3, 5});
}
}
[11] and [5, 5, 1]
[2, 1, 3] and [2, 4]
no split
[2, 1, 3] and [2, 4]: 6 kg each.
One row, the loop running down
Row i only reads row i - 1, so keep one boolean array can[s]. But can[s] reads can[s - w], a smaller index. If s went up, can[s - w] would already include the current bag, and the bag would be used twice. Going down, can[s - w] is still the old row.
| One bag of 2 kg | can[0] | can[2] | can[4] |
|---|---|---|---|
| before | ✓ | · | · |
| loop going up | ✓ | ✓ | ✓ (the bag used twice!) |
| loop going down | ✓ | ✓ | · |
import java.util.*;
public class Main {
static boolean canPartition(int[] w) {
int total = 0;
for (int x : w) total += x;
if (total % 2 == 1) return false;
int half = total / 2;
boolean[] can = new boolean[half + 1];
can[0] = true;
for (int x : w)
for (int s = half; s >= x; s--)
if (can[s - x]) can[s] = true;
return can[half];
}
public static void main(String[] args) {
System.out.println(canPartition(new int[]{1, 5, 11, 5}));
System.out.println(canPartition(new int[]{1, 2, 3, 5}));
System.out.println(canPartition(new int[]{1}));
System.out.println(canPartition(new int[]{2, 2}));
System.out.println(canPartition(new int[]{2, 2, 3, 5}));
}
}
true
false
false
true
false
The 41 bags that timed out, and the biggest LeetCode input (200 bags of up to 100 kg):
import java.util.*;
public class Main {
static boolean canPartition(int[] w) {
int total = 0;
for (int x : w) total += x;
if (total % 2 == 1) return false;
int half = total / 2;
boolean[] can = new boolean[half + 1];
can[0] = true;
for (int x : w)
for (int s = half; s >= x; s--)
if (can[s - x]) can[s] = true;
return can[half];
}
public static void main(String[] args) {
int[] bags = new int[41];
Arrays.fill(bags, 2);
bags[40] = 6;
long t0 = System.nanoTime();
boolean ok = canPartition(bags);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("41 bags: " + ok + ", " + ms + " ms");
int[] many = new int[200];
for (int i = 0; i < 200; i++) many[i] = (i * 37) % 100 + 1;
t0 = System.nanoTime();
ok = canPartition(many);
ms = (System.nanoTime() - t0) / 1000000;
System.out.println("200 bags: " + ok + ", " + ms + " ms");
}
}
41 bags: false, 0 ms
200 bags: true, 3 ms
The same solution in C++
The C++ version also shows the bitset trick: can |= can << x adds bag x to every reachable sum in one machine-word operation per 64 sums.
#include <bits/stdc++.h>
using namespace std;
// Partition equal subset sum: one row of booleans, the loop over s runs DOWN.
bool canPartition(const vector<int>& w) {
int total = accumulate(w.begin(), w.end(), 0);
if (total % 2 == 1) return false;
int half = total / 2;
vector<bool> can(half + 1, false);
can[0] = true;
for (int x : w)
for (int s = half; s >= x; s--)
if (can[s - x]) can[s] = true;
return can[half];
}
// The same with a bitset: bit s is set if s kg can be made. Shift-or adds one bag to every reachable sum.
bool canPartitionBits(const vector<int>& w) {
int total = accumulate(w.begin(), w.end(), 0);
if (total % 2 == 1) return false;
bitset<10001> can;
can[0] = 1;
for (int x : w) can |= can << x;
return can[total / 2];
}
int main() {
vector<vector<int>> tests = {{1, 5, 11, 5}, {1, 2, 3, 5}, {1}, {2, 2}, {2, 2, 3, 5}};
for (auto& t : tests) cout << boolalpha << canPartition(t) << " " << canPartitionBits(t) << "\n";
}
true true
false false
false false
true true
false false
The same solution in Python
Python's big integers work as a bitset too.
# Partition equal subset sum: one row of booleans, the loop over s runs DOWN.
def can_partition(w):
total = sum(w)
if total % 2 == 1:
return False
half = total // 2
can = [False] * (half + 1)
can[0] = True
for x in w:
for s in range(half, x - 1, -1):
if can[s - x]:
can[s] = True
return can[half]
# The same with a Python int as a bitset: bit s is set if s kg can be made.
def can_partition_bits(w):
total = sum(w)
if total % 2 == 1:
return False
bits = 1
for x in w:
bits |= bits << x
return (bits >> (total // 2)) & 1 == 1
for t in [[1, 5, 11, 5], [1, 2, 3, 5], [1], [2, 2], [2, 2, 3, 5]]:
print(can_partition(t), can_partition_bits(t))
True True
False False
False False
True True
False False
Three real bugs
Bug 1: the one-row loop going up. Bags [2, 6]: total 8, half 4, and no subset makes 4.
import java.util.*;
public class Main {
static boolean canPartition(int[] w) {
int total = 0;
for (int x : w) total += x;
if (total % 2 == 1) return false;
int half = total / 2;
boolean[] can = new boolean[half + 1];
can[0] = true;
for (int x : w)
for (int s = x; s <= half; s++)
if (can[s - x]) can[s] = true;
return can[half];
}
public static void main(String[] args) {
System.out.println(canPartition(new int[]{2, 6}));
}
}
true
true is wrong: can[2] became true from the 2 kg bag, then can[4] read the new can[2], using the same bag twice.
Bug 2: no odd check. [1, 2, 3, 5] has total 11; 11 / 2 is 5 in integer division, and 2 + 3 = 5.
import java.util.*;
public class Main {
static boolean canPartition(int[] w) {
int total = 0;
for (int x : w) total += x;
int half = total / 2;
boolean[] can = new boolean[half + 1];
can[0] = true;
for (int x : w)
for (int s = half; s >= x; s--)
if (can[s - x]) can[s] = true;
return can[half];
}
public static void main(String[] args) {
System.out.println(canPartition(new int[]{1, 2, 3, 5}));
}
}
true
true is wrong: the other group would weigh 6.
Bug 3: an array of size half.
import java.util.*;
public class Main {
static boolean canPartition(int[] w) {
int total = 0;
for (int x : w) total += x;
if (total % 2 == 1) return false;
int half = total / 2;
boolean[] can = new boolean[half];
can[0] = true;
for (int x : w)
for (int s = half; s >= x; s--)
if (can[s - x]) can[s] = true;
return can[half];
}
public static void main(String[] args) {
System.out.println(canPartition(new int[]{1, 5, 11, 5}));
}
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 11 out of bounds for length 11
at Main.canPartition(Main.java:13)
at Main.main(Main.java:17)
An array of length 11 has indexes 0 to 10; weight 11 needs index 11, so the length must be half + 1.
Complexity
| Approach | Time | Space | Big input |
|---|---|---|---|
| Take or skip (every subset) | O(2^n) | O(n) stack | 41 bags: Time Limit Exceeded |
| DP table (2D) | O(n × S/2) | O(n × S/2) | prints the groups too |
| One row, loop down | O(n × S/2) | O(S/2) | 200 bags: a few ms |
| Bitset (C++ / Python int) | O(n × S/64) | O(S/64) | ~64× fewer steps |
S is the total. This is pseudo-polynomial: fast because S ≤ 20,000. If the numbers could be up to 10^9, a table that wide wouldn't fit; then you'd need a different idea (for n ≤ 40, meet in the middle).
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
One row, s going up |
true for [2, 6] |
a bag used twice | for s = half down to w |
| No odd check | true for [1, 2, 3, 5] |
11 / 2 = 5 |
if (total % 2 == 1) return false |
new boolean[half] |
ArrayIndexOutOfBoundsException: Index 11 out of bounds for length 11 |
indexes 0 to half - 1 |
new boolean[half + 1] |
Forgetting can[0] = true |
always false |
nothing to build on | zero bags make 0 kg |
| Sorting and splitting greedily (biggest to the lighter friend) | wrong answers, e.g. false for [3, 3, 2, 2, 2] |
greedy can't undo a choice | DP |
| Recursion without memo on big inputs | Time Limit Exceeded | 2^n subsets |
table, or memo on (i, need) |
Mini project: the fair split app
Read a list of bag weights and print either no fair split or the two lists with their totals. Extension: if no equal split exists, print the split with the smallest difference (that is exactly Last Stone Weight II below).
Practice
1. Target Sum (LeetCode 494). Put + or - before every number so the total equals target; count the ways.
Solution
If P is the sum of the + numbers and N of the - numbers: P - N = target and P + N = total, so P = (total + target) / 2. Count the subsets with sum P: the same one row, with += instead of OR.
2. Last Stone Weight II (LeetCode 1049). Smash stones pairwise; the smallest possible last stone. The answer is total - 2 × (the reachable sum closest to half).
import java.util.*;
public class Main {
// Target Sum (LeetCode 494): signs + and -; P - N = target, P + N = total, so P = (total + target) / 2.
static int findTargetSumWays(int[] nums, int target) {
int total = 0;
for (int x : nums) total += x;
if (Math.abs(target) > total || (total + target) % 2 != 0) return 0;
int p = (total + target) / 2;
int[] ways = new int[p + 1];
ways[0] = 1;
for (int x : nums)
for (int s = p; s >= x; s--)
ways[s] += ways[s - x];
return ways[p];
}
// Last Stone Weight II (LeetCode 1049): the reachable sum closest to half.
static int lastStoneWeightII(int[] stones) {
int total = 0;
for (int x : stones) total += x;
int half = total / 2;
boolean[] can = new boolean[half + 1];
can[0] = true;
for (int x : stones)
for (int s = half; s >= x; s--)
if (can[s - x]) can[s] = true;
for (int s = half; s >= 0; s--)
if (can[s]) return total - 2 * s;
return total;
}
public static void main(String[] args) {
System.out.println(findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
System.out.println(findTargetSumWays(new int[]{1}, 1));
System.out.println(lastStoneWeightII(new int[]{2, 7, 4, 1, 8, 1}));
System.out.println(lastStoneWeightII(new int[]{31, 26, 33, 21, 40}));
}
}
5
1
1
5
3. Partition to K Equal Sum Subsets (LeetCode 698). With k groups the one-row table is not enough: use backtracking with pruning (episode 31) or bitmask DP (episode 77).
4. Print both groups for [3, 1, 4, 2, 2]. Run the walk-back program: [2, 1, 3] and [2, 4].
Quick quiz
Bags [2, 2, 3, 5]: total 12, half 6. Can they be split equally? A) Yes: 2 + 2 + 2 B) No: the total is odd C) No: no group makes 6 D) Yes: 3 + 3
Answer
C. The reachable sums are 0, 2, 3, 4, 5, 7, 8, 9, 10 and 12. 6 is missing, so the answer is false. An even total is necessary, but not enough.
Interview questions
- Why only one subset of
total / 2? The complement automatically sums to the other half. - State and recurrence?
can[i][s] = can[i-1][s] || (s ≥ w && can[i-1][s-w]),can[0][0] = true. - Why does the one-row loop run down?
can[s]readscan[s - w]; going down it is still the old row, so each item is used at most once. Going up gives the unbounded knapsack (coin change). - Complexity? O(n × S/2) time, O(S/2) space. Pseudo-polynomial.
- Early exit? Stop as soon as
can[half]becomes true; and if any number is bigger thanhalf, the answer isfalse. - How would you speed it up further? A bitset:
can |= can << x. - What if the numbers can be negative or huge? The table no longer works; use a hash set of reachable sums, or meet in the middle for n ≤ 40.
Glossary
| Term | Meaning |
|---|---|
| Subset | Some of the items, each at most once |
| Partition | Every item in exactly one group |
| Subset sum | Is there a subset with sum exactly T? |
| Complement | The items not chosen |
| Parity | Even or odd |
| State | (i, s): first i items, weight s |
| Recurrence | skip OR take |
| Base case | can[0][0] = true |
| Tabulation | Filling the table bottom-up |
| Rolling array | One row instead of the whole table |
| 0/1 knapsack | Each item taken 0 or 1 times; one-row loop goes down |
| Pseudo-polynomial | Fast because a number in the input is small |
| Bitset | A row of bits; bit s = sum s reachable |
Summary
- Odd total:
false. Even total: find a subset with sumtotal / 2. can[i][s] = can[i-1][s] OR can[i-1][s - w],can[0][0] = true. The recursion is right butO(2^n).- Walk back through the 2D table to print the two groups.
- One row,
sfromhalfdown tow:O(n × S)time,O(S)space. - Next episode: word break, DP over the prefixes of a string.