13.13 Bitmask Dynamic Programming
Most dynamic programming problems use states based on positions, intervals, capacities, or tree nodes.
13.13 Bitmask Dynamic Programming
Most dynamic programming problems use states based on positions, intervals, capacities, or tree nodes. Bitmask dynamic programming introduces a different idea: representing subsets as states.
This technique is particularly useful when the problem involves selecting, visiting, assigning, or arranging elements from a relatively small set. Instead of tracking individual decisions separately, an entire subset can be encoded as a single integer whose binary representation records which elements have already been chosen.
Bitmask dynamic programming is one of the most powerful tools for solving exponential-search problems. While the resulting algorithms are still exponential in the worst case, they often reduce infeasible brute-force searches into practical solutions for moderate input sizes.
Many classical problems, including the Traveling Salesman Problem, assignment problems, Hamiltonian paths, shortest superstrings, and set-cover variants, rely on bitmask dynamic programming.
Problem
How do we use dynamic programming when the state of a problem is determined by a subset of elements?
Understanding Bitmasks
Suppose a problem contains:
4 cities
A subset can be represented using four bits.
| Subset | Binary | Decimal |
|---|---|---|
| {} | 0000 | 0 |
| {0} | 0001 | 1 |
| {1} | 0010 | 2 |
| {0,1} | 0011 | 3 |
| {0,2} | 0101 | 5 |
| {0,1,2,3} | 1111 | 15 |
Each bit indicates whether an element belongs to the subset.
For example:
0101
means:
element 0 selected
element 2 selected
while elements:
1
3
remain unselected.
Why Bitmasks Are Useful
Consider:
choose any subset
of n elements
There are:
$$ 2^n $$
possible subsets.
Rather than storing sets explicitly, a bitmask represents every subset using a single integer.
Operations become extremely efficient.
Test Membership
mask&(1<<i) != 0
Add Element
mask | (1 << i)
Remove Element
mask & ^(1 << i)
Toggle Element
mask ^ (1 << i)
These operations execute in constant time.
Dynamic Programming on Subsets
The most common state is:
$$ dp[mask] $$
Meaning:
The optimal answer for the subset represented by mask.
This mirrors earlier state designs.
| Problem Type | State |
|---|---|
| Array | dp[i] |
| Grid | dp[i][j] |
| Interval | dp[l][r] |
| Tree | dp[node] |
| Subset | dp[mask] |
The challenge becomes defining transitions between subsets.
Example: Subset Sum
Suppose:
weights = [2,3,5]
Mask:
101
represents:
2 and 5 selected
The subset sum equals:
$$ 7 $$
A DP state may track whether a particular subset satisfies certain constraints.
Although not always the most efficient solution, this example illustrates the relationship between masks and subsets.
Example: Assignment Problem
Suppose:
n workers
n jobs
Each worker must receive exactly one job.
Brute force examines:
$$ n! $$
assignments.
Instead define:
$$ dp[mask] $$
Meaning:
Minimum cost after assigning jobs represented by mask.
The number of assigned jobs equals:
bits.OnesCount(mask)
which determines the next worker automatically.
Transition:
assign one new job
to the next worker.
The complexity becomes:
$$ O(n2^n) $$
rather than:
$$ O(n!) $$
This improvement is dramatic.
Traveling Salesman Problem
The Traveling Salesman Problem (TSP) is the most famous bitmask DP application.
Given:
- (n) cities
- pairwise distances
Find the shortest tour that visits every city exactly once and returns to the starting city.
Brute force:
$$ O(n!) $$
This quickly becomes impossible.
Bitmask dynamic programming reduces complexity substantially.
State Design
Define:
$$ dp[mask][u] $$
Meaning:
Minimum cost to visit all cities in mask and finish at city (u).
State components:
- visited cities
- current city
Both are necessary.
Knowing only the current city is insufficient.
Knowing only the subset is insufficient.
Together they uniquely define the subproblem.
Understanding the Transition
Suppose:
$$ dp[mask][u] $$
is known.
Choose an unvisited city:
$$ v $$
New mask:
$$ mask \cup {v} $$
Transition:
$$ dp[mask \cup {v}][v] = \min ( dp[mask][u] + dist[u][v] ) $$
Every step adds one city to the tour.
This recurrence systematically explores all Hamiltonian paths.
Complexity of TSP DP
Number of masks:
$$ 2^n $$
Number of ending cities:
$$ n $$
Transitions:
$$ n $$
Total complexity:
$$ O(n^2 2^n) $$
Memory:
$$ O(n2^n) $$
Although still exponential, this is dramatically better than:
$$ O(n!) $$
For:
$$ n \le 20 $$
the algorithm is often practical.
Iterating Through Subsets
A common pattern is:
for mask := 0; mask < (1 << n); mask++ {
...
}
This visits every subset exactly once.
For:
n = 3
the sequence becomes:
000
001
010
011
100
101
110
111
Every possible subset is processed.
Iterating Through Elements of a Subset
Suppose:
mask = 0b10110
To visit all selected elements:
for bit := 0; bit < n; bit++ {
if mask&(1<<bit) != 0 {
...
}
}
This pattern appears constantly in bitmask algorithms.
Enumerating Submasks
One of the most useful tricks in subset DP is iterating through all submasks.
for sub := mask; sub > 0; sub = (sub - 1) & mask {
...
}
This generates every subset contained within:
mask
without duplication.
Many advanced subset algorithms depend on this technique.
Example: Partitioning a Set
Suppose:
divide elements
into two groups
A recurrence might consider:
every possible submask
as one group.
Without efficient submask iteration, the algorithm becomes cumbersome.
The previous technique solves this elegantly.
State Compression
Bitmasks are often called:
state compression
because they compress a large amount of state information into a single integer.
For example:
selected elements
visited cities
completed tasks
active features
can all be represented using bits.
This dramatically reduces memory overhead.
Visualizing State Transitions
Consider:
n = 3
Possible masks:
000
001
010
011
100
101
110
111
Transitions add one element:
000 -> 001
000 -> 010
000 -> 100
001 -> 011
001 -> 101
...
The resulting structure forms a directed acyclic graph over subsets.
Bitmask DP computes shortest paths, longest paths, counts, or optimal values on this graph.
Common Patterns
Several state designs appear repeatedly.
Pure Subset State
$$ dp[mask] $$
Examples:
- subset feasibility
- partition problems
- counting arrangements
Subset + Position
$$ dp[mask][i] $$
Examples:
- TSP
- Hamiltonian path
- shortest superstring
Subset + Resource
$$ dp[mask][k] $$
Examples:
- assignment problems
- scheduling
- constrained optimization
Common Mistakes
Using Bitmask DP for Large N
State count:
$$ 2^n $$
grows rapidly.
Typical practical limits:
| N | States |
|---|---|
| 15 | 32,768 |
| 20 | 1,048,576 |
| 25 | 33,554,432 |
| 30 | 1,073,741,824 |
Beyond about twenty-five elements, memory and runtime often become problematic.
Incorrect Mask Updates
Forgetting to create a new mask frequently causes bugs.
Example:
newMask := mask | (1 << v)
must be computed correctly.
Missing State Information
Many problems require:
$$ dp[mask][position] $$
Attempting to use only:
$$ dp[mask] $$
often loses critical information.
Double Counting
Subset transitions can accidentally count equivalent solutions multiple times.
Carefully define state meaning and transition direction.
Recognizing Bitmask DP
Strong indicators include:
- subsets
- permutations
- visiting all nodes
- assignment problems
- Hamiltonian paths
- small (n)
- exponential brute force
- state compression
Whenever a problem asks:
which elements
have already been chosen?
a bitmask may provide an elegant state representation.
Complexity Analysis
For:
$$ n $$
elements:
State count:
$$ O(2^n) $$
Typical transitions:
$$ O(n) $$
Total complexity:
$$ O(n2^n) $$
or:
$$ O(n^2 2^n) $$
depending on recurrence structure.
Memory:
$$ O(2^n) $$
or:
$$ O(n2^n) $$
These complexities are exponentially better than many brute-force alternatives.
Takeaway
Bitmask dynamic programming extends dynamic programming to problems whose state is defined by a subset of elements. By encoding subsets as integers, large combinatorial search spaces can be explored systematically and efficiently. States such as (dp[mask]) and (dp[mask][i]) form the foundation of algorithms for assignment problems, Hamiltonian paths, shortest superstrings, and the Traveling Salesman Problem. Although the resulting algorithms remain exponential, they often transform completely impractical brute-force searches into solutions that work comfortably for moderate input sizes. Understanding bitmask DP is essential because it represents one of the most powerful applications of state compression in algorithm design.