Bitmask Dynamic Programming
Bitmask DP uses an integer’s bits to name a small subset, allowing transitions over chosen, visited, or assigned elements.
Why subsets become integers
For N small elements, bit i records whether element i belongs to a subset. The integer mask is a compact, hashable DP coordinate: membership uses mask&(1<<i), insertion uses mask|(1<<i), and removal uses mask^(1<<i) only when membership is known.
This technique is exponential, not magically fast. It is useful when N is roughly 15–22 depending on the transition and language. Always estimate 2^N times work per state before allocating the table.
- Bit i represents element i
- Operations change subsets in O(1)
- Feasibility depends exponentially on N
State and transition examples
Hamiltonian-path DP can define dp[mask][v] as routes visiting exactly mask and ending at v. A transition appends unseen u, producing mask|1<<u. Assignment DP may derive the next worker from popcount(mask), avoiding a redundant dimension.
Every bit must have one stable interpretation. Mixing visited cities with completed jobs in the same mask without a documented mapping makes transitions meaningless. Base states usually contain one selected start or the empty assignment.
- Name both mask and secondary coordinates
- Popcount can derive progress
- Base masks encode the first valid subproblem
Terms, operations, and practical uses
Bit representation
- MaskMask is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Set bitSet bit is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Full maskFull mask is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Transitions
- Add elementAdd element is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Submask iterationSubmask iteration is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Endpoint stateEndpoint state is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Engineering
- PopcountPopcount is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- State complexityState complexity is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
- Meet-in-the-middleMeet-in-the-middle is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Subset DP finds a shortest visit order
w=[[0,1,4],[1,0,2],[4,2,0]];n=3;inf=10**9;dp=[[inf]*n for _ in range(1<<n)];dp[1][0]=0
for mask in range(1<<n):
for u in range(n):
if dp[mask][u]<inf:
for v in range(n):
if not mask>>v&1:dp[mask|1<<v][v]=min(dp[mask|1<<v][v],dp[mask][u]+w[u][v])
ans=min(dp[-1][u]+w[u][0] for u in range(n))
print("Tour cost:",ans)#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
int main() {
int w[3][3]={{0,1,4},{1,0,2},{4,2,0}}, inf=1e9;
vector<vector<int>> dp(8,vector<int>(3,inf));
dp[1][0]=0;
for(int mask=0;mask<8;mask++) for(int u=0;u<3;u++) if(dp[mask][u]<inf) for(int v=0;v<3;v++) if(!(mask>>v&1)) dp[mask|1<<v][v]=min(dp[mask|1<<v][v],dp[mask][u]+w[u][v]);
int ans=inf;
for(int u=0;u<3;u++) ans=min(ans,dp[7][u]+w[u][0]);
cout << "Tour cost: " << ans << '\n';
}import java.util.*;
class Main {
public static void main(String[] args) {
int[][] w={{0,1,4},{1,0,2},{4,2,0}},dp=new int[8][3];
for(int[] row:dp) Arrays.fill(row,1_000_000_000);
dp[1][0]=0;
for(int mask=0;mask<8;mask++) for(int u=0;u<3;u++) if(dp[mask][u]<1_000_000_000) for(int v=0;v<3;v++) if((mask>>v&1)==0) dp[mask|1<<v][v]=Math.min(dp[mask|1<<v][v],dp[mask][u]+w[u][v]);
int ans=1_000_000_000;
for(int u=0;u<3;u++) ans=Math.min(ans,dp[7][u]+w[u][0]);
System.out.println("Tour cost: "+ans);
}
}Step through it
Running on cost matrix for 3 cities
Iterating submasks
To enumerate every nonempty submask of mask, repeatedly set sub=(sub−1)&mask. Each element has three roles across a pair (sub,mask): outside mask, inside both, or inside mask only, explaining why all submask transitions total O(3^N), not O(4^N).
Include sub=0 separately if the recurrence permits it and beware unsigned underflow. Complement operations must be restricted to the low N bits; raw ~mask also sets every higher machine bit.
- Use (sub−1)&mask
- All mask/submask pairs total 3^N
- Clamp complements to N bits
Ordering and memory
Transitions that add a bit can iterate masks by increasing popcount or simply increasing numeric value when every predecessor is mask with a bit removed. Top-down memoization visits only reachable subsets but adds recursion and hash overhead.
A table of 2^N·N 64-bit values grows quickly: N=22 already approaches hundreds of megabytes. Compress secondary state where the recurrence allows it and store infinity in a type that will not overflow when a transition cost is added.
- Predecessors remove at least one bit
- Memory can fail before time
- Guard infinity before addition
Testing subset invariants
Test N=0, one element, unreachable masks, duplicate costs, and cases where the optimal final element is not the cheapest local choice. Assert that dp[mask][v] is unreachable whenever v is not set in mask.
For small N, compare against permutation brute force. That independent oracle catches missing transitions, accidental reuse of an element, and precedence errors more reliably than testing only a familiar sample.
- Assert membership-state consistency
- Use brute force for tiny N
- Local cheapest choices need not be global
Practical mask discipline
Use parentheses around shifts inside compound expressions and choose an unsigned or sufficiently wide type for 1<<N. Name masks in binary in traces so a learner can connect integer index 13 with subset 1101. Precompute popcounts or valid-transition masks only when their reuse exceeds their storage cost.
Meet-in-the-middle may replace 2^N DP when state interaction splits cleanly, while SOS DP accelerates aggregate queries over every submask. These are different transformations; choosing them requires identifying whether the recurrence moves between subsets, partitions subsets, or asks for sums across subset relations.
A final audit should verify that every transition changes exactly the intended bits, never revisits a selected element, and never indexes a mask outside [0,2^N). Count reachable states during tests; an unexpectedly full or empty table often reveals a missing feasibility condition.
For Hamiltonian-path-style DP, the endpoint dimension is essential: the same visited subset can have different future costs depending on the last vertex. Initialize exactly one starting mask when the tour has a fixed origin, and add the return edge only after every vertex is visited. A common bug closes the cycle during intermediate transitions and counts a vertex twice. Symmetric distance matrices may allow fixing the start to remove rotational duplicates, but directed instances do not gain every symmetry. Validate on N=1, unreachable transitions, asymmetric weights, and a case where the locally cheapest next edge prevents the globally cheapest full tour.
- Parenthesize shift expressions
- Trace masks in binary
- Match the subset technique to the recurrence