Why does counting an integer from 0 to 2^n - 1 enumerate every subset of an n-element set?

## The bijection Choosing a subset of an n-element collection means answering n independent yes/no questions: is element 0 in, is element 1 in, and so on. There are 2 answers for each of n questions, hence 2^n possible subsets. An n-bit binary integer is precisely n independent yes/no digits. So the map "bit i is 1 means element i is in the subset" is a bijection between the integers 0..2^n - 1 and the subsets — every subset gets exactly one integer, every integer names exactly one subset. A counting loop visits every value in that range exactly once, in increasing numeric order. That is the entire enumeration: no stack, no visited set, no recursion, no partial results to copy. The loop counter *is* the state. ## Reading a mask To ask whether element i is in the subset named by `mask`, isolate its bit: `(mask & (1 << i)) != 0`. `1 << i` is a value with a single 1 at position i; ANDing keeps that bit only if the mask has it and clears everything else, so the result is either that power of two or zero. Scanning i from 0 to n-1 walks the subset's members. Two boundaries are worth saying out loud in an interview because they are where off-by-one errors live. Mask 0 has no bits set, so it is the empty subset — it is included, and an algorithm that assumes a non-empty selection must skip or guard it. Mask `(1 << n) - 1` has all n low bits set, so it is the full set, and it is the last value the loop visits. The loop bound is `< (1 << n)`, inclusive of `(1 << n) - 1`; writing `< (1 << n) - 1` silently drops the full set, and writing `<= (1 << n)` produces one mask with a bit outside the universe. ## The wrong answer this aims at Many candidates hear "enumerate all subsets" and immediately describe building a collection of collections — for each of 2^n possibilities, construct a fresh list of the chosen elements and store it. That is a legitimate output format when the caller genuinely wants the subsets themselves, but it is not the enumeration, and it is usually the expensive part. Materializing all subsets costs O(2^n * n) space; the counting loop costs O(1) extra space and only touches the elements it needs. On a scoring problem — pick the cheapest on-call team that covers every day of the week — you never need a list at all: you fold each candidate's contribution directly out of the bits and keep the best answer seen. Say that explicitly; it is what separates "I memorized the trick" from "I understand the encoding". ## Cost The outer loop is 2^n iterations. If the body scans all n bits, the total is O(2^n * n); if the body does constant work per mask, it is O(2^n). Both are exponential, and the base is what matters: for a twelve-person roster, 2^12 = 4096 masks, and with a 12-bit inner scan that is under 50,000 operations — free. Add ten more people and it is 4 million masks; add ten more again and it is 4 billion. The technique's shape is what makes it teachable, but its cost is what decides whether it is usable, and doubling every added element is not a gentle curve. A common refinement: if the inner scan is the bottleneck, precompute per-element contributions so the body is constant time, or derive each mask's value from a mask with one fewer bit, since removing the lowest set bit (`mask & (mask - 1)`) yields a smaller mask you have already processed. ## Order, and what the order does not give you The loop visits masks in increasing numeric order, which is *not* order by subset size. Mask 3 (two elements) comes before mask 4 (one element). If you need subsets grouped by cardinality — all singletons, then all pairs — numeric order will not deliver it; you either sort masks by the number of set bits or filter by that count on each pass. Candidates frequently assume the counting loop hands them a size-ordered enumeration and build a greedy algorithm on that false premise. One genuinely useful ordering property does hold: every mask that fits inside the low k bits is visited before any mask using bit k, because setting a higher bit makes the number larger. That is why the enumeration naturally processes subsets of a prefix before extending into new elements. ## Where the encoding pays beyond enumeration Because a subset is one integer, it is also a cheap key. A search over configurations — which of the switches are currently on — can record visited states as integers rather than as sets of sets, which turns an expensive structural hash and equality check into a machine-word comparison, and shrinks the memory footprint of the visited collection by an order of magnitude. That compactness is the same property the enumeration relies on: the set has been reduced to a number.