SyntaxPilot
Courses/DSA and Coding Problems/Lesson 70
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 70 of 90

Partition equal subset sum

queued

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 to total - 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 first i bags, and a weight s.
  • Recurrence: the rule for a state from smaller states: skip OR take.
  • Base case: can[0][0] = true (no bags make 0 kg) and can[0][s] = false for s > 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 s set means "s kg 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

  1. Odd total → false. Two equal whole numbers add up to an even number.
  2. 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 × 44 different (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

  1. Why only one subset of total / 2? The complement automatically sums to the other half.
  2. State and recurrence? can[i][s] = can[i-1][s] || (s ≥ w && can[i-1][s-w]), can[0][0] = true.
  3. Why does the one-row loop run down? can[s] reads can[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).
  4. Complexity? O(n × S/2) time, O(S/2) space. Pseudo-polynomial.
  5. Early exit? Stop as soon as can[half] becomes true; and if any number is bigger than half, the answer is false.
  6. How would you speed it up further? A bitset: can |= can << x.
  7. 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 sum total / 2.
  • can[i][s] = can[i-1][s] OR can[i-1][s - w], can[0][0] = true. The recursion is right but O(2^n).
  • Walk back through the 2D table to print the two groups.
  • One row, s from half down to w: O(n × S) time, O(S) space.
  • Next episode: word break, DP over the prefixes of a string.