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.
جو کم از کم جاننا ضروری ہے
- An `n`-bit mask encodes one subset of `n` candidate elements.
- Bit `i` tells whether element `i` is included.
- There are `2^n` possible subsets, so enumeration is feasible only for small `n`.
- 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.
اہم علامتیں
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
مختصر حل شدہ مثال
- For three items, masks `000` through `111` cover all subsets.
- Mask `101` means 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.
عام غلطیاں
- Students often forget the exponential `2^n` growth and try to use mask enumeration for large `n`.
- Students often confuse an item's index with the value stored at that index.
- Students often forget that mask `0` is a valid subset.
اس قسم کے سوال کو کیسے پہچانیں
- 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^n` states 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.