Imagine a control panel with n light switches. Each switch can be ON (1) or OFF (0). The entire panel state is just a sequence of bits:
Panel with 4 switches: [OFF, ON, ON, OFF]
As a number: 0 1 1 0 = 6 in binary
Switch 0 → bit 0 (2^0 = 1)
Switch 1 → bit 1 (2^1 = 2)
Switch 2 → bit 2 (2^2 = 4)
Switch 3 → bit 3 (2^3 = 8)
This is the core of Bitmask DP: we represent "which items are selected" as an integer, and use bit operations to efficiently track and transition between states.
The naive approach to tracking subsets would use sets or arrays:
# Slow: set operations, hashing
visited = {0, 2, 5}
if 3 not in visited:
visited.add(3)With bitmasks, the same operations are O(1):
# Fast: bit operations
visited = 0b100101 # {0, 2, 5}
if not (visited & (1 << 3)):
visited |= (1 << 3)Think of these as your "subset operations":
Operation Code Meaning
─────────────────────────────────────────────
Add i mask | (1 << i) Put i in the set
Remove i mask & ~(1 << i) Take i out
Check if i in mask & (1 << i) Is i present?
Toggle i mask ^ (1 << i) Flip i's membership
Full set (1 << n) - 1 All n elements
Empty set 0 Nothing selected
Count elements bin(mask).count('1') Set size
The insight: Every integer from 0 to 2^n - 1 represents a unique subset.
n = 3, elements = [A, B, C]
mask=0 (000): {} mask=4 (100): {C}
mask=1 (001): {A} mask=5 (101): {A, C}
mask=2 (010): {B} mask=6 (110): {B, C}
mask=3 (011): {A, B} mask=7 (111): {A, B, C}
The code writes itself:
for mask in range(1 << n):
subset = [items[i] for i in range(n) if mask & (1 << i)]The problem: Find the shortest path visiting ALL nodes in a graph.
The insight: State = (current_node, set_of_visited_nodes)
State (node=2, visited=0b101)
= "I'm at node 2, having visited nodes 0 and 2"
From here, I can go to node 1:
new_state = (node=1, visited=0b101 | 0b010)
= (node=1, visited=0b111)
= "Now at node 1, visited {0, 1, 2}"
Why BFS works: All edges have weight 1, so BFS finds shortest paths.
# Start from EVERY node (we can start anywhere)
for i in range(n):
queue.append((i, 1 << i, 0)) # (node, mask, distance)
while queue:
node, mask, dist = queue.popleft()
for neighbor in graph[node]:
new_mask = mask | (1 << neighbor)
if new_mask == (1 << n) - 1: # All visited!
return dist + 1
if (neighbor, new_mask) not in seen:
queue.append((neighbor, new_mask, dist + 1))Visual:
Graph: 0 — 1 — 2
Start: (0, 001, 0), (1, 010, 0), (2, 100, 0)
BFS Level 1:
From (0, 001): → (1, 011, 1)
From (1, 010): → (0, 011, 1), (2, 110, 1)
From (2, 100): → (1, 110, 1)
BFS Level 2:
From (1, 011): → (2, 111, 2) ← DONE! Distance = 2
The problem: Cover all required skills using minimum people. Each person has some subset of skills.
The insight: dp[skill_mask] = minimum team to achieve those skills
Required skills: [Python, Java, SQL]
Person 0: [Python] → mask = 001
Person 1: [Java, SQL] → mask = 110
Person 2: [Python, Java] → mask = 011
dp[000] = [] # No skills, no team needed
dp[001] = [0] # Just Python = Person 0
dp[011] = [2] # Python+Java = Person 2 (better than [0] + someone)
dp[110] = [1] # Java+SQL = Person 1
dp[111] = [1, 2] or [0, 1] # All skills
The transition:
for person_id, person_mask in enumerate(person_masks):
for current_mask, team in list(dp.items()):
new_mask = current_mask | person_mask
if new_mask not in dp or len(team) + 1 < len(dp[new_mask]):
dp[new_mask] = team + [person_id]Bitmask DP has exponential complexity. Here's the reality:
n 2^n Feasibility
──────────────────────────────
10 1,024 ✓ Fast
15 32,768 ✓ OK
18 262,144 ✓ Borderline
20 1,048,576 ⚠ Slow but doable
22 4,194,304 ✗ Too slow
25 33,554,432 ✗ Way too slow
When you see n ≤ 20 in constraints, think "bitmask DP is probably intended."
❌ if mask & i: # WRONG: i is not a bit
✅ if mask & (1 << i): # RIGHT: 1 << i is the bit❌ State = just the visited mask
(Same mask can be reached from different nodes!)
✅ State = (current_node, visited_mask)❌ queue = [(0, 1, 0)] # Start only from node 0
✅ # Start from ALL nodes
for i in range(n):
queue.append((i, 1 << i, 0))❌ for mask, team in dp.items():
dp[new_mask] = ... # Modifying during iteration!
✅ for mask, team in list(dp.items()): # Copy to list first
dp[new_mask] = ...| Clue | Pattern |
|---|---|
| "All subsets" or "power set" | Subset Enumeration |
| "Visit all nodes", n ≤ 12 | BFS + Bitmask |
| "Minimum team to cover all", m ≤ 16 | Set Cover DP |
| "Partition into k equal groups" | Bitmask + DP |
| "Assign n tasks to n workers" | Bitmask permutation |
Think of bitmask DP as navigating a hypercube:
n=3: 8 states (vertices of a cube)
011 -------- 111
/ | / |
001 -------- 101 |
| | | |
| 010 -------|- 110
| / | /
000 -------- 100
Transitions: Add one element = move along an edge
Full mask (111) = goal state
Every problem is about finding the best path from some starting vertex to the target vertex.
BITMASK DP PATTERNS:
1. SUBSET ENUM 2. BFS + BITMASK 3. SET COVER DP
mask=0 to 2^n-1 (node, mask) dp[mask] = team
↓ ↓ ↓
decode to subset BFS layers person by person
↓ ↓ ↓
collect results first full_mask min team for full
Bitmask DP is about encoding set membership as integers for O(1) transitions. The key is recognizing when your state is "which items are selected" and n is small enough (≤ 20).