Enumerating Submasks

The loop

for (int s = mask; s; s = (s - 1) & mask) {
    // s runs over all NON-EMPTY submasks of mask, in decreasing order
}
// handle s == 0 separately if the empty submask matters

Or, including zero:

for (int s = mask; ; s = (s - 1) & mask) {
    // ...
    if (s == 0) break;
}

Why it works

s - 1 clears the lowest set bit of s and sets all bits below it. ANDing with mask keeps only bits that belong to the mask. The result is the next smaller submask — and every submask is visited exactly once, in strictly decreasing numeric order.

The $3^n$ bound

${\sum }_{\text{mask}\subseteq [n]}{2}^{|\text{mask}|}={\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^k=3^n.$

Each element is in one of three states: in the submask, in the mask but not the submask, or in neither. So iterating over all masks and all their submasks is $O(3^n)$, not $O(4^n)$.

$n$	$2^n$	$3^n$	$4^n$
15	$3.3\cdot 10^4$	$1.4\cdot 10^7$	$10^9$
18	$2.6\cdot 10^5$	$3.9\cdot 10^8$	—
20	$10^6$	$3.5\cdot 10^9$	—

So $3^n$ is affordable up to $n\approx 17$.

What it is for

Set partitioning

// minimum number of valid groups covering `full`
dp[0] = 0;
for (int mask = 1; mask < (1 << n); mask++)
    for (int s = mask; s; s = (s - 1) & mask)
        if (valid[s]) dp[mask] = min(dp[mask], dp[mask ^ s] + 1);

Symmetry breaking: always assign the lowest set bit of mask to the current group. That avoids generating the same partition in $k!$ orders and typically gives a 10× speedup:

int low = mask & -mask;
for (int s = mask; s; s = (s - 1) & mask)
    if (s & low) { /* only submasks containing the lowest element */ }

Subset convolution

$h(S)={\sum }_{T\subseteq S}f(T)g(S\setminus T)$

is $O(3^n)$ directly, or $O(2^n{n}^2)$ with ranked SOS DP — the difference between $n=17$ and $n=22$.

Other uses

• Steiner tree — merge two sub-trees at a vertex.
• TSP with grouped cities, set cover, exact cover.
• Counting matchings in a small graph by splitting off one vertex’s partner.
• Any DP whose transition splits a set into two parts.

Supermasks

The dual loop, over all masks containing mask within $n$ bits:

for (int s = mask; s < (1 << n); s = (s + 1) | mask) { /* ... */ }

Also $O(3^n)$ in total. See Enumerating Supermasks.

Submasks of a fixed size

Use Gosper’s hack to iterate all $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ masks with exactly $k$ bits:

for (unsigned v = (1u<<k)-1; v < (1u<<n); ) {
    // process v
    unsigned c = v & -v, r = v + c;
    v = r | (((v ^ r) >> 2) / c);
}

$O(1)$ per mask, in increasing numeric order.

Avoiding the $3^n$ entirely

When the transition is a subset sum rather than an arbitrary split, SOS DP does the same work in $O(2^{n}n)$:

$F(S)={\sum }_{T\subseteq S}f(T)\text{in }O(2^{n}n).$

Before writing a $3^n$ loop, ask whether the inner sum is really an arbitrary partition or just a subset aggregation — the latter is much cheaper.

See also: SOS DP · Bitmask DP · Enumerating Supermasks