Partition into equal subsets and the bitset trick

Why this matters

Suppose three friends share a bill of 1, 5, 11 and 5 units of money, and each person should pay half of the total. Can the four items be split into two piles with the same sum? This is the partition problem. It shows up when you divide work, cost or storage into two halves that must match.

The naive way to answer is to try every way of putting each item in pile A or pile B. With 4 items there are 16 choices, which is easy. With 200 items there are more than 10 to the power of 60 choices, which no computer can check. Dynamic programming (DP, a method that solves a big problem by saving answers to smaller parts) avoids this by asking a smaller question: which totals can I reach so far?

This lesson builds that DP and then shows a shortcut in C++. The shortcut stores the reachable totals as bits, and one shift and one OR per number update all of them at once. Here the table is stored as a row of bits.

The idea: which totals can be reached?

Start with the simplest version of the question. Given a list of numbers, can some group of them add up to a target number? This is called the subset-sum problem. A group can be empty, and each number can be used at most once.

The partition problem is subset-sum in disguise. If the total of all numbers is T, two equal piles each add to T / 2. So the question becomes: can some group add up to T / 2? If T is odd, the answer is no straight away, because two equal whole-number piles cannot add up to an odd total.

Take the list 1, 5, 11, 5. The total is 22, so each pile must add to 11. Build the set of reachable totals one number at a time. Begin with only the empty group, which reaches 0.

The last row contains 11, so the answer is yes. The piles are 11 and 1, 5, 5. Each row comes from the row above it. When a new number x arrives, every total already in the set gives a new total by adding x. The new set is the old set plus those shifted totals.

Look at the step where 5 arrives after 1, 5 and 11. The old set is 0, 1, 5, 6, 11, 12, 16, 17. Adding 5 to each total gives 5, 6, 10, 11, 16, 17, 21, 22. Put both lists together and remove repeats, and you get the new set in the last row.

Turning the table into a row of numbers

A standard DP table has one row per number and one column per total. Each cell is true or false. Cell (i, s) is true when some group using only the first i numbers adds to s.

Each row needs only the row above it, so one row is enough. Keep a single array ok where ok[s] is true when the total s is reachable. For each number x, you must set ok[s] to true when ok[s - x] was already true.

There is one trap. If you walk the totals from small to large, a number can be used twice. Say x is 1 and ok[0] is true. Setting ok[1] makes ok[2] true on the same pass, because ok[1] is now true. That would mean the number 1 was used twice. The fix is to walk from large totals down to small ones, so each update reads a value that was set before this number arrived.

Here is that version in plain C++.

#include <iostream>
#include <numeric>
#include <vector>
 
bool canPartition(const std::vector<int>& nums) {
    int total = std::accumulate(nums.begin(), nums.end(), 0);
    if (total % 2 != 0) return false;
    int half = total / 2;
 
    std::vector<char> ok(half + 1, 0);
    ok[0] = 1;
    for (int x : nums) {
        for (int s = half; s >= x; --s) {   // downwards, so each number is used once
            if (ok[s - x]) ok[s] = 1;
        }
    }
    return ok[half];
}
 
int main() {
    std::cout << std::boolalpha;
    std::cout << canPartition({1, 5, 11, 5}) << "\n";
}

The output is:

true

This works, and it is fast enough for most inputs. The bitset trick below does the same job with a shorter loop body and a smaller array.

The bitset trick

A std::bitset<N> from the <bitset> header is a fixed-size row of N bits. Each bit is 0 or 1, and you can read or set a bit by its index, the same way you read an array. The size N must be a number known at compile time. The header also gives you whole-row operations: | (OR), & (AND) and << (shift).

A left shift bits << x moves every bit x places towards larger indexes. If bit 3 is 1, then after << 2 bit 5 is 1. In other words, every reachable total s moves to s + x. That is exactly the step we need. The new reachable totals are the old ones shifted by x.

An OR keeps a bit that was 1 in either row. So reachable |= reachable << x means: the new set is the old set, plus every old total shifted by x. One line does the whole update for one number.

This line is safe for the same reason the downward loop was. The expression reachable << x builds a new, temporary row from the old values before the OR writes anything. So no total gets shifted twice for the same number.

Here is the complete program.

#include <bitset>
#include <cstddef>
#include <iostream>
#include <numeric>
#include <vector>
 
// Largest sum we can track. Bit i is 1 when some group of numbers adds to i.
constexpr std::size_t kMaxSum = 20000;
 
bool canPartition(const std::vector<int>& nums) {
    int total = std::accumulate(nums.begin(), nums.end(), 0);
    if (total % 2 != 0) return false;        // an odd total cannot split evenly
    int half = total / 2;
 
    std::bitset<kMaxSum + 1> reachable;
    reachable[0] = true;                     // the empty group makes sum 0
    for (int x : nums) {
        reachable |= reachable << x;         // add x to every reachable sum, keep the old ones
    }
    return reachable[half];
}
 
int main() {
    std::vector<int> a{1, 5, 11, 5};
    std::vector<int> b{1, 2, 3, 5};
    std::vector<int> c{2, 4, 6, 10};
    std::cout << std::boolalpha;
    std::cout << "[1, 5, 11, 5]: " << canPartition(a) << "\n";
    std::cout << "[1, 2, 3, 5]: " << canPartition(b) << "\n";
    std::cout << "[2, 4, 6, 10]: " << canPartition(c) << "\n";
    std::cout << "sizeof(reachable): " << sizeof(std::bitset<kMaxSum + 1>) << " bytes\n";
}

Compile it with a C++20 compiler and warnings on:

g++ -std=c++20 -Wall -o partition partition.cpp
./partition

The output is:

[1, 5, 11, 5]: true
[1, 2, 3, 5]: false
[2, 4, 6, 10]: false
sizeof(reachable): 2504 bytes

The compiler printed nothing, so the file has no warnings under -Wall.

To see the bits change, run the same shift on a smaller row of 23 bits and print the set bits after each number.

#include <bitset>
#include <iostream>
#include <vector>
 
int main() {
    std::bitset<23> r;
    r[0] = true;
    for (int x : std::vector<int>{1, 5, 11, 5}) {
        r |= r << x;
        std::cout << "after " << x << ": ";
        for (int s = 0; s < 23; ++s)
            if (r[s]) std::cout << s << " ";
        std::cout << "\n";
    }
}

The output matches the table from the first section:

after 1: 0 1 
after 5: 0 1 5 6 
after 11: 0 1 5 6 11 12 16 17 
after 5: 0 1 5 6 10 11 12 16 17 21 22 

Each line is one step of the table. The set bits are the reachable totals.

Worked example: a case that fails

Take 2, 4, 6, 10. Every number is even, so every group adds to an even total. The total of all four is 22, so the target is 11, which is odd. No group of even numbers can add to an odd number. The program correctly prints false.

The bitset loop still runs over all the numbers before it gives the answer. The check for an odd total is what lets it stop early when the total is odd. Here the total is even, so the loop runs, and the bit for 11 is never set.

Now try a list where a single big number is too large to matter: 3, 34, 4, 12, 5, 2. The total is 60 and the target is 30. The number 34 is larger than 30, so it can never be part of a pile that adds to 30. The other numbers add to only 26. No group reaches 30, so the answer is false. The shift for 34 pushes its bits past index 30, and those bits never come back down, because every number is positive. Those bits do no harm.

Memory and speed notes

The bitset is a compact array. Its size is kMaxSum + 1 bits, which is 20001 bits. On this machine with g++ 15.2, sizeof reports 2504 bytes. The same table as a std::vector<char> takes about 20001 bytes, and a std::vector<int> with the same number of entries takes about 80004 bytes. Each bit uses one eighth of the space of a char.

The bitset is also fast for a simple reason. The processor works on 64 bits at a time. A bitset of 20001 bits is stored in 313 such groups, so one shift or OR touches about 313 machine words. The array loop tests one total at a time, so it does far more small steps.

On this machine, I built the two versions with -O2 and ran 200 numbers, each up to 100, with a total of at most 20000. The bitset version took about 0.05 ms per run. The array version took about 0.3 ms per run. The bitset was about six to seven times faster. Your numbers will differ with the machine and the input, so measure before you rely on the ratio.

There are three costs to keep in mind.

The size must be a compile-time constant. You cannot write std::bitset<n> with n read from input. The compiler error for that case is shown in the mistakes section below. The fixed size is the price of the speed.

The bitset always does the full work. It shifts all 20001 bits for every number, even when the numbers are small. The array loop stops at half, so it does less work for small totals. For a small input, a plain array can be the better choice.

The bitset only answers yes or no. It does not record which numbers made the target. If you need the actual piles, you need to store extra information, such as the choice made for each total, which is covered by a later lesson on reconstructing answers.

Common mistakes

Forgetting the empty group

If you forget reachable[0] = true, no total is ever reached. Every shift of an empty row is still empty.

missingZero [1,1] target 2 -> 0

The correct answer for the list 1, 1 and target 2 is 1, because both numbers together make 2. The output is wrong because nothing starts the chain. Set the bit for 0 before the loop.

Walking upwards in the array version

If you walk the array from small totals to large ones (for (int s = x; s <= half; ++s)), a number can be used twice.

upwardArray [1,5] target 3 -> 1

The true answer is 0. The groups of 1, 5 add to 0, 1, 5 or 6, and none adds to 3. The upward walk let the number 1 be used again, so it reached 3 as 1 + 1 + 1. Walk downwards, as the code in this lesson does.

The bitset version has no such bug, because the shift always works from the old row.

Forgetting the odd-total check

If the total is odd, the code computes total / 2 with rounding down. For 1, 2 the total is 3 and the target becomes 1, which is reachable. The program then wrongly says that 1, 2 can be split into two equal piles.

[1,2] without parity test -> 1
[1,2] with parity test -> 0

Keep the check if (total % 2 != 0) return false; before you compute the target.

A size that is not a constant

A bitset needs its size at compile time. Here is a program that uses a variable.

#include <bitset>
#include <iostream>
 
int main() {
    int limit = 20000;
    std::bitset<limit + 1> reachable;
    std::cout << reachable.size() << "\n";
}

The first lines of the compiler's real output are:

badsize.cpp: In function ‘int main()’:
badsize.cpp:6:26: error: the value of ‘limit’ is not usable in a constant expression
    6 |     std::bitset<limit + 1> reachable;
      |                          ^
badsize.cpp:5:9: note: ‘int limit’ is not const

The fix is to make the value constexpr, as the program in this lesson does with kMaxSum. The bitset then has a fixed size that must be large enough for the largest target.

Using the wrong shift direction

reachable >> x moves bits towards smaller indexes. That maps each total s to s - x, which is the opposite of adding a number. The program still compiles and runs, but the answers are wrong. Use << for adding a number to a total.

Practice

Exercise 1

Can 3, 1, 1, 2, 2, 1 be split into two equal piles? Work out the total and the target first. Then find a pile.

Show the answer

The total is 10, so each pile must add to 5. The pile 3, 2 adds to 5, and the rest, 1, 1, 2, 1, also adds to 5. The answer is true. The program prints true for this input.

Exercise 2

Why does 2, 2, 3 return false without any DP at all?

Show the answer

The total is 7, which is odd. Two whole-number piles cannot have equal sums when the total is odd, so the answer is false right away. The function returns in the parity check before the bitset is built.

Exercise 3

The list 2, 4, 6, 10 has an even total. Why is the answer still false?

Show the answer

The total is 22, so the target is 11, which is odd. Every number in the list is even, so every group adds to an even number. No group can add to 11, so the answer is false.

Exercise 4

Suppose the bitset is std::bitset<1001> and you add four numbers, each 500. The total is 2000 and the target is 1000. Does reachable[1000] give the right answer, and what does reachable.test(1001) do?

Show the answer

The bit for 1000 is inside the row of 1001 bits, so reachable[1000] gives true, which is correct, because 500 + 500 makes 1000. The bit for 1001 is outside the row. The test function checks the index and throws std::out_of_range. The error text is bitset::test: __position (which is 1001) >= _Nb (which is 1001) on this compiler. The operator[] form does not check the index, so you must keep the target inside the size.

Exercise 5

For 200 numbers and a row of 20001 bits, how many 64-bit word operations does one full run of the bitset loop perform?

Show the answer

Each shift or OR touches 313 words, because 20001 bits divided into groups of 64 needs 313 groups. Each number causes one shift and one OR, so the total is about 200 times 2 times 313, which is 125200 word operations. The per-number cost does not depend on the values, only on the size of the row.

Summary

• The partition problem asks for a group of numbers that adds to half the total. An odd total is an immediate false.
• Build reachable totals one number at a time, and keep the old totals as well as the shifted new ones.
• In an array version, walk downwards so each number is used once.
• In a std::bitset, reachable |= reachable << x does the whole update for one number.
• The bitset needs a compile-time size, costs the same work for every input, and gives only a yes or no answer.