Enumerating Subsets & Submasks
O(2^n), submasks O(3^n) totalThe bit tricks every mask problem is built on: iterate all 2^n subsets of n items, test/set/clear single bits, and, the one people forget, enumerate all submasks of a given mask in O(3^n) total over all masks with the s = (s-1) & m loop. For n up to ~20, brute force over subsets is often the intended solution, not a fallback.
// use it on
CSES: Apple Division ↗
n <= 20 apples split into two groups: try every subset as group one and take the best difference. 2^20 subsets is about a million, comfortably fast.
// the code
// all subsets of n items
for (int mask = 0; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++)
if (mask >> i & 1) { /* item i is in this subset */ }
}
// all submasks of m (skips the empty set; O(3^n) over all m)
for (int s = m; s; s = (s - 1) & m) { /* use submask s */ }
// common one-liners
int cnt = __builtin_popcount(mask); // number of set bits
int low = mask & -mask; // lowest set bit
bool has = mask >> i & 1; // is bit i set?
int with_i = mask | (1 << i), without_i = mask & ~(1 << i);// more bitmask