Bitmasks For Subset Representation - Learning Module

Loading content...

0/279

Bitmask DP Introduction

The Pinnacle of Bitmask Techniques

Bitmask Dynamic Programming represents the culmination of everything we've learned about bitmask subset representation. It's a technique that elegantly solves problems where:

We must select or arrange elements from a small set (typically n ≤ 20)
The solution depends on which elements have been used/visited
Exponential enumeration seems necessary, but overlapping subproblems exist

Bitmask DP transforms the 'visited set' or 'selected subset' into an integer state, enabling O(1) state transitions and compact memoization. Problems that seem to require brute-force search over n! permutations or 2ⁿ subsets become tractable—reduced to O(n² × 2ⁿ) or O(n × 2ⁿ), which is dramatically faster.

What You Will Master

By the end of this page, you will understand: (1) the core concept of using bitmasks as DP states, (2) how to identify problems suitable for bitmask DP, (3) the Traveling Salesman Problem as the canonical bitmask DP example, (4) assignment problems and their bitmask DP solutions, and (5) complexity analysis and practical limits.

The Core Concept: Subsets as States

Traditional DP states are often simple: an index i, a remaining capacity, a position in a grid. Bitmask DP extends this by making the state include a subset of elements—typically 'which elements have been visited/selected so far.'

The insight: Instead of tracking the set as an array or hash set (which would make states incomparable or require complex hashing), we track it as an integer bitmask. Since integers can be array indices, our DP table is simply dp[mask] or dp[mask][i].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Traditional DP: state is index or count
// dp[i] = best value considering elements 0..i
const traditionalDP = new Array(n).fill(0);
 
// Bitmask DP: state INCLUDES a subset
// dp[mask] = best value for the subset encoded in mask
const bitmaskDP = new Array(1 << n).fill(0);
 
// Often combined with position or last element:
// dp[mask][i] = best value when elements in 'mask' are used
//               and 'i' is the last/current element
const bitmaskDP2D = Array.from(
    { length: 1 << n },
    () => new Array(n).fill(Infinity)
);
 
/**
 * State transitions in bitmask DP:
 * 
 * If we're at state (mask, current) and want to visit element 'next':
 * - Check if 'next' is available: ((mask >> next) & 1) === 0
 * - New state: (mask | (1 << next), next)
 * - Update: dp[newMask][next] = min/max(..., dp[mask][current] + cost)
 */
 
// Example transition loop
/*
for (let mask = 0; mask < (1 << n); mask++) {
    for (let current = 0; current < n; current++) {
        if (((mask >> current) & 1) === 0) continue; // current must be in mask
        
        for (let next = 0; next < n; next++) {
            if ((mask >> next) & 1) continue; // next must NOT be in mask
            
            const newMask = mask | (1 << next);
            const newCost = dp[mask][current] + cost[current][next];
            dp[newMask][next] = Math.min(dp[newMask][next], newCost);
        }
    }
}
*/

Why Bitmask States Work

The key insight is that the optimal solution for a subset depends only on WHICH elements are in the subset, not HOW we selected them. This 'optimal substructure' over subsets enables DP. The bitmask encoding makes states comparable (equality is just integer comparison) and indexable (directly use as array index).

Identifying Bitmask DP Problems

Not every problem benefits from bitmask DP. Here's how to recognize when it's the right tool:

Signs a Problem Calls for Bitmask DP

•Small n (typically ≤ 20): The 2ⁿ state space must be tractable. n = 20 gives ~10⁶ states, n = 25 gives ~33 million.
•Subset selection required: The solution involves choosing WHICH elements to include, not just how many.
•Order matters within subset: Problems like TSP where we need the minimum cost PATH through cities.
•Assignment/matching: Pair elements from set A to set B (e.g., tasks to workers, jobs to machines).
•Counting with constraints: Count ways to select elements satisfying relationship constraints.
•All elements must be covered: 'Visit all cities', 'complete all tasks', 'cover all positions'.

Classic Bitmask DP Problem Types
Problem Type	State	Complexity	Example
Traveling Salesman	dp[mask][last]	O(n² × 2ⁿ)	Minimum tour through all cities
Assignment Problem	dp[mask]	O(n × 2ⁿ)	Assign n tasks to n workers
Hamiltonian Path	dp[mask][last]	O(n² × 2ⁿ)	Path visiting all vertices exactly once
Set Cover	dp[mask]	O(m × 2ⁿ)	Minimum subsets to cover all elements
Counting Arrangements	dp[mask][last]	O(n² × 2ⁿ)	Permutations satisfying constraints

The n ≤ 20 Rule

With n = 20, we have 2²⁰ ≈ 10⁶ subsets. At n = 25, that's 33 million. At n = 30, over a billion. Beyond n ≈ 20-23, bitmask DP becomes impractical. For larger n, consider approximation algorithms, heuristics, or problem-specific optimizations.

The Canonical Example: Traveling Salesman Problem

The Traveling Salesman Problem (TSP) asks: given n cities and the distances between each pair, what's the shortest route that visits every city exactly once and returns to the origin?

Without bitmask DP: We'd enumerate all n! permutations. For n = 10, that's 3.6 million routes. For n = 15, that's 1.3 trillion—completely intractable.

With bitmask DP: We compute optimal partial paths for each subset of cities. Complexity drops to O(n² × 2ⁿ). For n = 15, that's 15² × 2¹⁵ ≈ 7.4 million operations—very tractable.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * Traveling Salesman Problem using Bitmask DP
 * 
 * State: dp[mask][i] = minimum cost to visit all cities in 'mask',
 *                      ending at city 'i'
 * 
 * Base case: dp[1 << 0][0] = 0 (start at city 0, only city 0 visited)
 * 
 * Transition: For each subset 'mask' containing 'i':
 *   For each city 'j' not in 'mask':
 *     dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j],
 *                                   dp[mask][i] + dist[i][j])
 * 
 * Answer: min over all i of (dp[fullMask][i] + dist[i][0])
 * 
 * Time: O(n² × 2ⁿ)
 * Space: O(n × 2ⁿ)
 */
function tsp(dist: number[][]): number {
    const n = dist.length;
    const INF = Infinity;
    const fullMask = (1 << n) - 1;
    
    // dp[mask][i] = min cost to reach state (mask, i)
    const dp: number[][] = Array.from(
        { length: 1 << n },
        () => new Array(n).fill(INF)
    );
    
    // Base case: start at city 0
    dp[1][0] = 0;  // mask = 0b1, only city 0 visited, cost = 0
    
    // Process all subsets in increasing order
    for (let mask = 1; mask < (1 << n); mask++) {
        for (let last = 0; last < n; last++) {
            // Skip if 'last' is not in mask
            if (((mask >> last) & 1) === 0) continue;
            
            // Skip impossible states
            if (dp[mask][last] === INF) continue;
            
            // Try extending to each unvisited city
            for (let next = 0; next < n; next++) {
                // Skip if 'next' is already visited
                if ((mask >> next) & 1) continue;
                
                const newMask = mask | (1 << next);
                const newCost = dp[mask][last] + dist[last][next];
                
                dp[newMask][next] = Math.min(dp[newMask][next], newCost);
            }
        }
    }
    
    // Find minimum cost to complete the tour
    // Must visit all cities and return to city 0
    let answer = INF;
    for (let last = 0; last < n; last++) {
        if (dp[fullMask][last] !== INF) {
            answer = Math.min(answer, dp[fullMask][last] + dist[last][0]);
        }
    }
    
    return answer;
}
 
// Example: 4 cities with distance matrix
const distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
];
 
console.log(`Minimum tour cost: ${tsp(distances)}`);  // 80
 
// Trace: Optimal tour is 0 → 1 → 3 → 2 → 0
// Cost: 10 + 25 + 30 + 15 = 80

Understanding the state space:

Let's trace through the states for n = 4 cities (0, 1, 2, 3):

Mask (binary)	Visited Cities	Valid 'last' values
0001	{0}	0 (base case)
0011	{0, 1}	1
0101	{0, 2}	2
1001	{0, 3}	3
0111	{0, 1, 2}	1, 2
1011	{0, 1, 3}	1, 3
1101	{0, 2, 3}	2, 3
1111	{0, 1, 2, 3}	1, 2, 3

For each state (mask, last), we store the minimum cost to reach that configuration.

Why Not Just Store dp[mask]?

We need dp[mask][last] because different ending cities lead to different future options. The cost to reach {0,1,2} ending at city 1 differs from ending at city 2, and the optimal continuation differs too. The 'last' dimension captures this.

Reconstructing the Optimal Path

Computing the optimal value is half the challenge. Often we need the actual solution—the sequence of cities, the assignment mapping, etc. We reconstruct this by tracing back through our DP table.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
 * TSP with full path reconstruction
 */
function tspWithPath(dist: number[][]): { cost: number; path: number[] } {
    const n = dist.length;
    const INF = Infinity;
    const fullMask = (1 << n) - 1;
    
    // DP tables
    const dp: number[][] = Array.from(
        { length: 1 << n },
        () => new Array(n).fill(INF)
    );
    
    // Parent tracking: parent[mask][i] = previous city
    const parent: number[][] = Array.from(
        { length: 1 << n },
        () => new Array(n).fill(-1)
    );
    
    // Base case
    dp[1][0] = 0;
    
    // Fill DP table
    for (let mask = 1; mask < (1 << n); mask++) {
        for (let last = 0; last < n; last++) {
            if (((mask >> last) & 1) === 0) continue;
            if (dp[mask][last] === INF) continue;
            
            for (let next = 0; next < n; next++) {
                if ((mask >> next) & 1) continue;
                
                const newMask = mask | (1 << next);
                const newCost = dp[mask][last] + dist[last][next];
                
                if (newCost < dp[newMask][next]) {
                    dp[newMask][next] = newCost;
                    parent[newMask][next] = last;  // Track predecessor
                }
            }
        }
    }
    
    // Find best final city and total cost
    let minCost = INF;
    let lastCity = -1;
    
    for (let i = 0; i < n; i++) {
        const totalCost = dp[fullMask][i] + dist[i][0];
        if (totalCost < minCost) {
            minCost = totalCost;
            lastCity = i;
        }
    }
    
    // Reconstruct path by backtracking
    const path: number[] = [0];  // End at city 0
    let currentCity = lastCity;
    let currentMask = fullMask;
    
    while (currentCity !== -1 && currentCity !== 0) {
        path.push(currentCity);
        const prevCity = parent[currentMask][currentCity];
        currentMask = currentMask ^ (1 << currentCity);  // Remove current city
        currentCity = prevCity;
    }
    path.push(0);  // Start at city 0
    path.reverse();
    
    return { cost: minCost, path };
}
 
// Example
const dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
];
 
const result = tspWithPath(dist);
console.log(`Cost: ${result.cost}`);
console.log(`Path: ${result.path.join(' → ')}`);
 
// Output:
// Cost: 80
// Path: 0 → 1 → 3 → 2 → 0

Space Optimization Trade-off

The parent table doubles our space usage. If memory is tight but you need the path, you can reconstruct by re-checking which transition led to optimal values (costs more time but saves space). Alternatively, only store parent pointers for the final answer reconstruction.

The Assignment Problem

Another classic bitmask DP problem: given n workers and n tasks, with cost[i][j] being the cost for worker i to perform task j, find the minimum total cost to assign each worker to exactly one task (and each task to exactly one worker).

The Hungarian algorithm solves this in O(n³), but bitmask DP provides an intuitive O(n × 2ⁿ) solution that's faster for small n and easier to understand.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/**
 * Assignment Problem: Assign n workers to n tasks
 * 
 * State: dp[mask] = minimum cost to assign workers 0..k-1 to the tasks in 'mask'
 *        where k = popcount(mask) (number of workers assigned so far)
 * 
 * Key insight: We assign workers in order (0, then 1, then 2, ...).
 * When assigning worker i, we know exactly i tasks are already assigned (mask has i bits set).
 * 
 * Base case: dp[0] = 0 (no workers assigned, no tasks used, zero cost)
 * 
 * Transition: For each mask with k bits set (k workers already assigned):
 *   Worker k is next to assign. For each unassigned task j:
 *   dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + cost[k][j])
 * 
 * Answer: dp[fullMask] (all n tasks assigned)
 * 
 * Time: O(n × 2ⁿ)
 * Space: O(2ⁿ)
 */
function assignmentProblem(cost: number[][]): number {
    const n = cost.length;
    const INF = Infinity;
    const fullMask = (1 << n) - 1;
    
    // dp[mask] = min cost to reach this assignment state
    const dp = new Array(1 << n).fill(INF);
    dp[0] = 0;
    
    for (let mask = 0; mask < fullMask; mask++) {
        if (dp[mask] === INF) continue;
        
        // Count assigned workers = popcount(mask)
        const worker = popcount(mask);
        
        // Try assigning this worker to each unassigned task
        for (let task = 0; task < n; task++) {
            if ((mask >> task) & 1) continue;  // Task already assigned
            
            const newMask = mask | (1 << task);
            dp[newMask] = Math.min(dp[newMask], dp[mask] + cost[worker][task]);
        }
    }
    
    return dp[fullMask];
}
 
function popcount(x: number): number {
    let count = 0;
    while (x) {
        x &= x - 1;
        count++;
    }
    return count;
}
 
// Example: 4 workers, 4 tasks
const costs = [
    [9, 2, 7, 8],   // Worker 0's cost for tasks 0, 1, 2, 3
    [6, 4, 3, 7],   // Worker 1
    [5, 8, 1, 8],   // Worker 2
    [7, 6, 9, 4]    // Worker 3
];
 
console.log(`Minimum assignment cost: ${assignmentProblem(costs)}`);  // 13
 
// Optimal: W0→T1(2), W1→T0(6), W2→T2(1), W3→T3(4) = 13
 
/**
 * Assignment with reconstruction
 */
function assignmentWithSolution(cost: number[][]): { 
    cost: number; 
    assignment: number[] 
} {
    const n = cost.length;
    const INF = Infinity;
    const fullMask = (1 << n) - 1;
    
    const dp = new Array(1 << n).fill(INF);
    const parent = new Array(1 << n).fill(-1);  // Which task was added
    dp[0] = 0;
    
    for (let mask = 0; mask < fullMask; mask++) {
        if (dp[mask] === INF) continue;
        
        const worker = popcount(mask);
        
        for (let task = 0; task < n; task++) {
            if ((mask >> task) & 1) continue;
            
            const newMask = mask | (1 << task);
            const newCost = dp[mask] + cost[worker][task];
            
            if (newCost < dp[newMask]) {
                dp[newMask] = newCost;
                parent[newMask] = task;
            }
        }
    }
    
    // Reconstruct assignment
    const assignment = new Array(n);
    let mask = fullMask;
    for (let worker = n - 1; worker >= 0; worker--) {
        const task = parent[mask];
        assignment[worker] = task;
        mask ^= (1 << task);  // Remove this task
    }
    
    return { cost: dp[fullMask], assignment };
}
 
const solution = assignmentWithSolution(costs);
console.log(`
Optimal assignment:`);
solution.assignment.forEach((task, worker) => {
    console.log(`  Worker ${worker} → Task ${task} (cost: ${costs[worker][task]})`);
});

Assignment vs TSP State Difference

In TSP, we need dp[mask][last] because the last city affects where we can go next. In assignment, we only need dp[mask] because the next worker is determined by popcount(mask)—workers are assigned in fixed order, so we always know who's next.

Counting with Bitmask DP

Bitmask DP isn't just for optimization—it excels at counting problems where we need to count arrangements, paths, or configurations satisfying constraints.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/**
 * Count Hamiltonian Paths in a Graph
 * 
 * A Hamiltonian path visits every vertex exactly once.
 * 
 * State: dp[mask][v] = number of paths that:
 *   - Visit exactly the vertices in 'mask'
 *   - End at vertex 'v'
 * 
 * Time: O(n² × 2ⁿ)
 */
function countHamiltonianPaths(adj: boolean[][]): number {
    const n = adj.length;
    const fullMask = (1 << n) - 1;
    
    // dp[mask][v] = count of paths for (mask, v)
    const dp: number[][] = Array.from(
        { length: 1 << n },
        () => new Array(n).fill(0)
    );
    
    // Base case: single vertex paths
    for (let v = 0; v < n; v++) {
        dp[1 << v][v] = 1;  // One path: just vertex v
    }
    
    // Process subsets by size (or just iterate through all)
    for (let mask = 1; mask < (1 << n); mask++) {
        for (let last = 0; last < n; last++) {
            if (((mask >> last) & 1) === 0) continue;
            if (dp[mask][last] === 0) continue;
            
            // Extend path to each adjacent unvisited vertex
            for (let next = 0; next < n; next++) {
                if ((mask >> next) & 1) continue;          // Already visited
                if (!adj[last][next]) continue;            // No edge
                
                const newMask = mask | (1 << next);
                dp[newMask][next] += dp[mask][last];
            }
        }
    }
    
    // Sum all paths that visit all vertices
    let total = 0;
    for (let v = 0; v < n; v++) {
        total += dp[fullMask][v];
    }
    
    return total;
}
 
// Example: Complete graph on 4 vertices
const complete4: boolean[][] = [
    [false, true, true, true],
    [true, false, true, true],
    [true, true, false, true],
    [true, true, true, false]
];
 
// For complete graph K_n, there are n!/2 Hamiltonian paths
// (Each path counted in 2 directions, so n! permutations / 2)
// Wait, we're counting directed paths, so it's n! = 24 for n=4
 
console.log(`Hamiltonian paths in K4: ${countHamiltonianPaths(complete4)}`);  // 24
 
/**
 * Count permutations where adjacent elements differ by at most k
 */
function countConstrainedPermutations(n: number, k: number): number {
    const fullMask = (1 << n) - 1;
    
    // dp[mask][last] = count of permutations of elements in mask, ending with last
    const dp: number[][] = Array.from(
        { length: 1 << n },
        () => new Array(n).fill(0)
    );
    
    // Base case: single element
    for (let v = 0; v < n; v++) {
        dp[1 << v][v] = 1;
    }
    
    for (let mask = 1; mask < (1 << n); mask++) {
        for (let last = 0; last < n; last++) {
            if (((mask >> last) & 1) === 0) continue;
            if (dp[mask][last] === 0) continue;
            
            for (let next = 0; next < n; next++) {
                if ((mask >> next) & 1) continue;
                
                // Constraint: |last - next| <= k
                if (Math.abs(last - next) <= k) {
                    dp[mask | (1 << next)][next] += dp[mask][last];
                }
            }
        }
    }
    
    let total = 0;
    for (let v = 0; v < n; v++) {
        total += dp[fullMask][v];
    }
    return total;
}
 
console.log(`Permutations of {0..3} with adjacent diff ≤ 1: ${countConstrainedPermutations(4, 1)}`);
// Valid: 0123, 0132 is invalid (3-1=2>1), etc.

Optimization Techniques for Bitmask DP

The base O(n² × 2ⁿ) complexity can often be improved or the constant factors reduced. Here are key optimizations:

Performance Optimizations

•Skip invalid states early: Check if (dp[mask] === INF) continue before the inner loop to avoid processing unreachable states.
•Use bitwise popcount: For assignment-style problems, popcount(mask) is called frequently. Use lookup tables or hardware intrinsics.
•Process subsets by size: If transitions only go from smaller to larger subsets, process by popcount level.
•Prune with lower bounds: Skip states where the remaining potential can't beat the current best.
•Space optimization: If you only need the previous 'level' of subsets, you may be able to reduce space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * TSP with pruning: skip states that can't beat the current best
 */
function tspOptimized(dist: number[][]): number {
    const n = dist.length;
    const INF = Infinity;
    const fullMask = (1 << n) - 1;
    
    // Precompute lower bounds: minimum distance from any city to any other
    const minEdge = Math.min(...dist.flat().filter(d => d > 0));
    
    const dp: number[][] = Array.from(
        { length: 1 << n },
        () => new Array(n).fill(INF)
    );
    dp[1][0] = 0;
    
    let globalBest = INF;
    
    // Iterate by subset size for better cache behavior
    for (let size = 1; size <= n; size++) {
        for (let mask = 0; mask < (1 << n); mask++) {
            if (popcount(mask) !== size) continue;
            
            for (let last = 0; last < n; last++) {
                if (((mask >> last) & 1) === 0) continue;
                if (dp[mask][last] === INF) continue;
                
                // Pruning: can we possibly beat globalBest?
                const remaining = n - size;
                const lowerBound = dp[mask][last] + remaining * minEdge + dist[last][0];
                if (lowerBound >= globalBest) continue;
                
                if (mask === fullMask) {
                    // Complete tour
                    globalBest = Math.min(globalBest, dp[mask][last] + dist[last][0]);
                    continue;
                }
                
                for (let next = 0; next < n; next++) {
                    if ((mask >> next) & 1) continue;
                    
                    const newMask = mask | (1 << next);
                    const newCost = dp[mask][last] + dist[last][next];
                    
                    if (newCost < dp[newMask][next]) {
                        dp[newMask][next] = newCost;
                    }
                }
            }
        }
    }
    
    return globalBest;
}
 
function popcount(x: number): number {
    let c = 0;
    while (x) { x &= x-1; c++; }
    return c;
}

Memory Access Patterns

Processing masks by popcount (subset size) improves cache behavior—states at the same level are accessed together. Additionally, using flat arrays instead of 2D arrays can improve performance due to better memory locality.

Common Patterns and Templates

Here are reusable patterns that appear across many bitmask DP problems:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/**
 * TEMPLATE 1: Minimum/Maximum over all paths (TSP-style)
 * 
 * State: dp[mask][last] = optimal value for (visited set, ending position)
 * Use when: Order matters, we need to end at different positions
 */
function templatePathOptimization(n: number, cost: (from: number, to: number) => number): number {
    const dp = Array.from({ length: 1 << n }, () => Array(n).fill(Infinity));
    
    // Base: start at each position
    for (let start = 0; start < n; start++) {
        dp[1 << start][start] = 0; // or initial cost
    }
    
    for (let mask = 1; mask < (1 << n); mask++) {
        for (let last = 0; last < n; last++) {
            if (!((mask >> last) & 1)) continue;
            if (dp[mask][last] === Infinity) continue;
            
            for (let next = 0; next < n; next++) {
                if ((mask >> next) & 1) continue;
                
                const newMask = mask | (1 << next);
                dp[newMask][next] = Math.min(
                    dp[newMask][next],
                    dp[mask][last] + cost(last, next)
                );
            }
        }
    }
    
    // Combine final answers
    return Math.min(...dp[(1 << n) - 1]);
}
 
/**
 * TEMPLATE 2: Assignment (workers in order)
 * 
 * State: dp[mask] = optimal value for assigning first k workers to tasks in mask
 *        where k = popcount(mask)
 * Use when: One set is assigned in fixed order
 */
function templateAssignment(n: number, cost: (worker: number, task: number) => number): number {
    const dp = Array(1 << n).fill(Infinity);
    dp[0] = 0;
    
    for (let mask = 0; mask < (1 << n) - 1; mask++) {
        if (dp[mask] === Infinity) continue;
        
        const worker = popcount(mask);
        
        for (let task = 0; task < n; task++) {
            if ((mask >> task) & 1) continue;
            
            const newMask = mask | (1 << task);
            dp[newMask] = Math.min(dp[newMask], dp[mask] + cost(worker, task));
        }
    }
    
    return dp[(1 << n) - 1];
}
 
/**
 * TEMPLATE 3: Subset sum/composition
 * 
 * State: dp[mask] = whether/how subset 'mask' can be achieved
 * Use when: Subsets partition into groups, or combine additively
 */
function templateSubsetComposition(n: number, groupMasks: number[]): number {
    // Example: Minimum groups to cover all elements
    const fullMask = (1 << n) - 1;
    const dp = Array(1 << n).fill(Infinity);
    dp[0] = 0;
    
    for (let mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] === Infinity) continue;
        
        for (const group of groupMasks) {
            // Can only add group if it doesn't overlap
            if ((mask & group) === 0) {
                const newMask = mask | group;
                dp[newMask] = Math.min(dp[newMask], dp[mask] + 1);
            }
        }
    }
    
    return dp[fullMask];
}
 
function popcount(x: number): number {
    let c = 0;
    while (x) { x &= x-1; c++; }
    return c;
}

Summary: Bitmask DP Mastery

Bitmask Dynamic Programming is a powerful technique that sits at the intersection of combinatorics, set theory, and optimization. Let's consolidate the key concepts:

Key Takeaways

•Core Concept: Use bitmasks as DP states to represent 'which elements are selected/visited'. This enables O(1) state comparison and direct array indexing.
•Problem Recognition: Look for small n (≤20), subset selection, ordering constraints, assignment matching, or counting arrangements.
•TSP Pattern: dp[mask][last] tracks the optimal path to visit exactly 'mask' vertices, ending at 'last'. Complexity O(n² × 2ⁿ).
•Assignment Pattern: dp[mask] tracks optimal assignment of first k workers to tasks in 'mask'. Complexity O(n × 2ⁿ).
•Counting: Same state structure, but accumulate counts instead of optimizing values.
•Reconstruction: Track parent pointers to recover the actual solution, not just the optimal value.
•Optimization: Skip invalid states, prune with bounds, process by subset size for cache efficiency.

Bitmask DP Complexity Reference
Problem Type	State	Time	Space
TSP/Hamiltonian	dp[mask][last]	O(n² × 2ⁿ)	O(n × 2ⁿ)
Assignment	dp[mask]	O(n × 2ⁿ)	O(2ⁿ)
Subset Composition	dp[mask]	O(m × 2ⁿ)*	O(2ⁿ)

Module Complete: Bitmasks for Subset Representation

Congratulations! You've mastered one of the most elegant techniques in algorithmic problem-solving. From representing sets as integers, through efficient enumeration and O(1) operations, to the powerful bitmask DP paradigm—you now have a complete toolkit for problems involving small-set combinatorics. This knowledge separates proficient programmers from algorithm experts.