Bitmasks for subsets
In one line
A set of up to about 20 items can be written as one integer where bit i means item i is included, so counting from 0 to 2^n - 1 walks through every subset.
What it is
A bitmask is an integer used as a set. For a list of n items, bit i of the mask is 1 when item i is in the subset and 0 when it is not. For items [a, b, c], the mask 101 (5) means {a, c} and 110 (6) means {b, c}.
Every integer from 0 to 2^n - 1 is a different mask, and together they cover all 2^n subsets exactly once. Set operations become single instructions: union is OR, intersection is AND, difference is a & ~b, and adding or removing an item is setting or clearing one bit.
Why interviewers ask
Subset problems appear constantly: pick a team, choose features, try all combinations. Bitmask enumeration is a short, iterative, recursion-free way to try them all, and it is the foundation of bitmask DP. Interviewers also check that you know the limits: 2^n grows fast, so this works for n up to about 20, not 100.
How it works
- 1Number the items 0 to n - 1.
- 2Loop mask from 0 to (1 << n) - 1. Each value is one subset.
- 3Inside the loop, item i is in the subset when (mask >> i) & 1 is 1. Build the subset or evaluate it directly.
- 4To walk only the subsets of a given mask m, start sub = m and repeat sub = (sub - 1) & m until it reaches 0. Subtracting 1 and ANDing with m jumps straight to the next smaller submask.
- 5If you loop over every mask and, inside, every submask, the total work is 3^n rather than 4^n, because each item is either outside the mask, in the mask but not the submask, or in both.
Worked example · All subsets of [a, b, c]
- n = 3, so masks run from 0 to 7.
- mask 0 = 000: {}. mask 1 = 001: {a}. mask 2 = 010: {b}. mask 3 = 011: {a, b}.
- mask 4 = 100: {c}. mask 5 = 101: {a, c}. mask 6 = 110: {b, c}. mask 7 = 111: {a, b, c}.
- That is 8 = 2^3 subsets, each listed once.
- Submasks of 101: start at 101, then (101 - 1) & 101 = 100 & 101 = 100, then (100 - 1) & 101 = 011 & 101 = 001, then (001 - 1) & 101 = 000. So the submasks are 101, 100, 001, 000: {a, c}, {c}, {a}, {}.
Picture it
Picture a row of n tick boxes on a form. Each way of ticking them is one subset, and reading the ticks as a binary number gives you a unique ID for that choice. Counting from 0 to 2^n - 1 is just trying every possible way of filling in the form.
Reference code
def all_subsets(items):
n = len(items)
result = []
for mask in range(1 << n): # 0 .. 2^n - 1
subset = [items[i] for i in range(n) if mask >> i & 1]
result.append(subset)
return result
def submasks(mask):
# every subset of the bits in mask, largest first, ending with 0
sub = mask
while True:
yield sub
if sub == 0:
break
sub = (sub - 1) & mask
print(all_subsets(["a", "b", "c"]))
# [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]
print([bin(s) for s in submasks(0b101)])
# ['0b101', '0b100', '0b1', '0b0']
all_subsets turns each number into a subset by reading its bits. submasks uses the (sub - 1) & mask step, which visits only subsets of mask and never wastes time on others.
Key patterns
Enumerate all subsets
When: n is at most about 20 and you must check every combination
How: for mask in range(1 << n), then test (mask >> i) & 1 for each item. O(n * 2^n).
Enumerate submasks
When: For a fixed set, you need all of its subsets (common in DP over partitions)
How: sub = (sub - 1) & mask until 0. Over all masks this totals O(3^n).
Meet in the middle
When: n is around 40, too large for 2^n but fine for 2^(n/2)
How: Split the items into two halves, enumerate each half's 2^20 subset sums, sort one side and binary search or two-pointer to combine.
Mask as a visited set
When: Search or DP needs to remember which items are already used
How: Store the used items as a mask in the state, so the state is hashable and fast to copy. Leads into bitmask DP.
Real-world use
Discord permissions
Discord represents a role's permissions as a bitfield integer; combining roles is a bitwise OR and checking a permission is an AND with that permission's bit.
Redis bitmaps for user activity
SETBIT login:2026-10-24 <user_id> 1 marks a user active for a day. BITOP AND across several days' bitmaps gives users active on all of them, and BITCOUNT counts them, using one bit per user.
Chess engine bitboards
Engines like Stockfish represent the 64 squares as a 64-bit integer per piece type. Attacked squares, occupied squares and legal moves are computed with AND, OR and shifts on whole boards at once.
Feature combination testing
QA tools that test every combination of a handful of feature flags (say 10 flags, 1,024 combinations) generate them by counting through bitmasks.
In a project
A meal-kit startup offers 15 optional add-ons, each with a price and a calorie count. Customers want the most add-ons that fit a budget of 30 dollars and a 900-calorie limit, and the catalogue changes weekly.
- Number the add-ons 0 to 14, so every selection is a mask from 0 to 2^15 - 1 = 32,767.
- Loop over all masks; for each, sum the price and calories of the set bits and skip it if either limit is exceeded.
- Keep the valid mask with the most set bits, breaking ties by lowest price.
- Precompute each mask's totals from mask & (mask - 1) (the mask without its lowest bit) to make each step O(1) instead of O(n).
Impact: About 33,000 masks are checked in a few milliseconds, the answer is guaranteed optimal rather than a greedy guess, and the code is under 20 lines, so it is easy to rerun whenever the catalogue changes.
Trade-offs
Use it when
- n is small (about 20 or less) and every combination must be checked
- You want an iterative, recursion-free subset generator
- Subsets are DP state or hash keys and need to be compact
Avoid it when
- n is large; 2^30 is over a billion masks
- Most subsets can be pruned early; backtracking with pruning will skip whole branches
- The set has more than 64 items in a language with fixed-width integers
Cost: All subsets: O(2^n) masks and O(n * 2^n) to build or check them. All submasks of all masks: O(3^n). Space O(1) beyond the output.
Common mistakes
- Writing range(2 << n) or range(1 << n + 1) and generating twice as many masks as needed.
- Forgetting the empty subset (mask 0) or the full set (mask 2^n - 1) when the problem needs them.
- Using 2^n in Python, which is XOR, instead of 1 << n or 2 ** n.
- Writing the submask loop as while sub > 0 and then forgetting to handle the empty submask if it is needed.
- Trying bitmask enumeration for n = 40 and timing out; switch to meet in the middle or DP.
Interview questions
Quick revision
- Bit i set in mask means item i is chosen.
- for mask in range(1 << n) covers all 2^n subsets.
- Union a | b, intersection a & b, difference a & ~b.
- Submasks: sub = (sub - 1) & mask, total O(3^n) over all masks.
- Practical limit: n around 20 to 25 for 2^n.
- n around 40: meet in the middle with 2^(n/2) per half.
- In Python, 2^n is XOR; use 1 << n.
Check yourself
1. For items [a, b, c] with a as bit 0, which subset does mask 6 represent?
2. How many masks does a loop over all subsets of 4 items visit?
3. What is the total work to enumerate every submask of every mask of n bits?
4. What does (sub - 1) & mask do in submask enumeration?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.