Chapter 88

Home

Refactoring: Subset Enumeration with Bits

Naively checking all 2ᴺ subsets is O(2ᴺ × N). The for (sub = mask; sub; sub = (sub-1) & mask) trick enumerates only subsets of a given mask in O(2^popcount) — no iteration over bits.

Before: Check All Masks

C++ — O(2ᴺ) checking all masks

for (int sub = 0; sub < (1 << n); sub++) {
    if ((sub & mask) != sub) continue;  // not a subset
    // process sub
}
// Checks 2^N masks — wasteful

After: Subset Enumeration Trick

C++ — enumerate subsets of mask only

for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // process sub — it's a subset of mask
}
// Also include the empty set if needed:
// for (int sub = mask; ; sub = (sub - 1) & mask) {
//     process sub;
//     if (sub == 0) break;
// }

// Only enumerates true subsets of mask — O(2^popcount(mask))
// For mask = 10101: visits 10101, 10100, 10001, 10000,
//                   00101, 00100, 00001, 00000

Key Takeaways