Neel Mishra
← All Posts
DSA · Bit Manipulation· Part 17 of 32

Subset Enumeration Patterns

May 2026 · 24 min read

Bitmask DP starts with one skill: enumerating exactly the masks you need, no more and no less. The difference between O(4^n), O(3^n), and O(n * 2^n) often comes down to choosing the right enumeration loop.

All Masks

A mask from 0 to (1 << n) - 1 represents one subset of an n-element set.

for (int mask = 0; mask < (1 << n); ++mask) {
    // process subset represented by mask
}

Iterating Set Bits

Use m & -m or __builtin_ctz to visit only elements present in the subset.

for (int m = mask; m; m &= m - 1) {
    int bit = m & -m;
    int i = __builtin_ctz(m);
    // element i is present
}

Enumerating Submasks

The classic loop visits every non-empty submask of mask.

for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // sub is a non-empty submask of mask
}

// Include zero too:
for (int sub = mask;; sub = (sub - 1) & mask) {
    // process sub
    if (sub == 0) break;
}

Why All Mask/Submask Pairs Are O(3^n)

For each bit, there are three possibilities across a pair (sub, mask): absent from mask, present in mask but absent from sub, or present in both. Therefore the total number of pairs is 3^n.

for (int mask = 0; mask < (1 << n); ++mask) {
    for (int sub = mask; sub; sub = (sub - 1) & mask) {
        // total O(3^n)
    }
}

Enumerating Supersets

To visit masks that contain base, enumerate submasks of the remaining free bits.

int full = (1 << n) - 1;
int free_bits = full ^ base;

for (int add = free_bits;; add = (add - 1) & free_bits) {
    int sup = base | add;
    // sup contains base
    if (add == 0) break;
}

Splitting a Mask

Many DP transitions split a set into two parts: sub and mask ^ sub. To avoid double-counting unordered splits, enforce an ordering such as sub < other.

for (int sub = (mask - 1) & mask; sub; sub = (sub - 1) & mask) {
    int other = mask ^ sub;
    if (sub > other) continue; // unordered split only once
}

Masks by Popcount

Some DP states must be processed by subset size.

vector<vector<int>> by_size(n + 1);
for (int mask = 0; mask < (1 << n); ++mask) {
    by_size[__builtin_popcount(mask)].push_back(mask);
}

for (int sz = 0; sz <= n; ++sz) {
    for (int mask : by_size[sz]) {
        // process masks with exactly sz elements
    }
}

Recognition Guide

Practice Problems