Algorithms / Subset Enumeration Bitmask
Least You Need to Know: Bitmask Subset Enumeration and Used-Set State
Enumerating masks from 0 to 2^n - 1 gives every subset of an n-element set. Interviews use this for subset generation, used-element state, and small-state dynamic programming where each bit records a chosen item.
Least you need to know
- An
n-bit mask encodes one subset ofncandidate elements. - Bit
itells whether elementiis included. - There are
2^npossible subsets, so enumeration is feasible only for smalln. - The zero mask is the empty set and a full low-bit mask is the whole set.
- Bitmask states also represent which elements have already been used in permutation or DP problems.
Key notation
- 0 ... 2^n - 1 — all subset masks for n items
- mask >> i & 1 — whether item i is included
- full_mask — mask with the low n bits all set
Worked example
- For three items, masks
000through111cover all subsets. - Mask
101means take items 0 and 2 but not 1. - A loop over all masks therefore enumerates all subsets.
- The same idea tracks which jobs or cities have already been used in a state-space search.
Common mistakes
- Students often forget the exponential
2^ngrowth and try to use mask enumeration for largen. - Students often confuse an item's index with the value stored at that index.
- Students often forget that mask
0is a valid subset.
How to recognize it
- The prompt asks for all subsets, all used/un-used configurations, or a small-state DP over chosen items.
- Each choice is binary: in or out.
- The problem size is small enough that
2^nstates might be acceptable.
Next recommended lesson
Continue through this topic with Least You Need to Know: Subsets, Combinations, and Choose/Skip Search.
Least You Need to Know: Subsets, Combinations, and Choose/Skip SearchRelated lessons
Keep going with nearby lessons in the same topic.