Enumerate subsets by mask

33 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Take three items: a, b, c. How many different groups can you make from them, counting the empty group and the full group? You would probably start listing: nothing, a, b, c, a and b, a and c, b and c, all three. That is 8 groups. Now try it with 5 items. Most people lose track somewhere around the twentieth group, write one twice, and miss another. The job needs a system that never skips and never repeats.

The counting itself is easy. Each item has two choices, in or out, and the choices are independent, so with n items there are 2 × 2 × … × 2 groups:

number of subsets = 2ⁿ

For 3 items that is 8, for 10 items 1,024, for 20 items about a million. The question is how to produce them in order without a pencil-and-paper mess.

Build the structure, one piece at a time

The structure is nothing more than an ordinary integer, read as a row of switches. A number in binary is a list of bits, each 0 or 1. Give each item one bit position: bit 0 is a, bit 1 is b, bit 2 is c. Read a bit of 1 as "this item is in the group" and 0 as "it is out". The integer is called a mask.

Now simply count from 0 upwards and read off the switches:

To turn a mask into its subset, test each bit: item i is included when (mask >> i) & 1 equals 1. That is the whole machine: a counter from 0 to 2ⁿ − 1 and one bit test per item.

Why it is correct

The invariant is that each mask names exactly one subset, and each subset has exactly one mask. Both directions follow from the way binary numbers work. A number between 0 and 2ⁿ − 1 has exactly one binary spelling with n bits, so one mask cannot describe two subsets. In the other direction, write a 1 for every chosen item and a 0 for every other item; that spelling is a number in the range, so every subset is reached. Because counting visits each integer once, every subset appears exactly once and none is forgotten.

The ordering is a bonus. Counting up means the subsets come out in a fixed, predictable order, which makes the mask a reliable label: if you need to remember "I have already handled the group {a, c}", you store the number 5.

Why it is fast

There are 2ⁿ masks and reading one takes n bit tests, so listing every subset costs about n · 2ⁿ steps. That sounds large, and it is, but it is the size of the answer itself; nothing can list a million subsets in fewer than a million steps. What the mask buys is zero overhead: no recursion, no stack of partial choices, no duplicate checks. The hand method needed a growing list to compare against, which is far worse.

Masks also make a perfect key for a table. A problem that needs "the best result using exactly this set of items" can keep an array indexed by mask, with 2ⁿ entries, and look up or update any set in constant time. That is the door to bitmask dynamic programming, where a solution for a mask is built from the solutions for masks with one bit fewer.

How to recognise it in an interview

The tell is a small n, usually 20 or less, together with words like "all subsets", "any combination", "choose a group of" or "assign each item to one of two sides". When you hear that, say: "with n that small I can afford every subset; I will represent each one as an n-bit mask and loop from 0 to 2ⁿ − 1".

In Subsets the mask loop is the entire answer. In Maximum Product of Word Lengths each word is turned into a 26-bit mask of the letters it uses, and two words share no letter exactly when the AND of their masks is 0, so the mask is used as a fingerprint rather than as a counter. In Partition to K Equal Sum Subsets the mask records which numbers have already been placed, and the search state is the mask plus the running sum.

02The idea in one line

Masks 0..2^n−1 encode every subset; bit i means item i is in.

Reach for it when: Subsets, maximum product of word lengths, beautiful arrangement, can partition.

Cost: O(2^n · n) time.

03The walk-through, step by step

The video works one example: Subsets of [a,b,c] by mask 000..111. These are its captions in order, so you can follow without the video or check a step you missed.

1. Masks 0 … 2ⁿ−1 are all the subsets: each bit is one include/exclude choice
2. mask 000 → {}
3. mask 001 → {a}
4. mask 010 → {b}
5. mask 011 → {a,b}
6. mask 100 → {c}
7. mask 101 → {a,c}
8. mask 110 → {b,c}
9. mask 111 → {a,b,c}
10. 8 masks, 8 distinct subsets, no recursion and no duplicates
11. O(2ⁿ · n) to list them; a mask is also a perfect DP state key

04Asked at Google

4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Bit Manipulation: XOR cancels pairs, Bit tricks (n & (n−1), masks).