Why is N limited to around 20?

The state space holds 2^N subsets. At N = 20 that is about a million states, which is fine; at N = 30 it is a billion, which exceeds both memory and time. The exponent is in the number of states, not in the transition.

What does the mask represent?

One bit per element, set when that element has been used or visited. Pairing the mask with the last chosen element, as dp[mask][i], is the standard state for travelling-salesman and assignment problems.

Which bit operations do I need?

Setting with mask | (1 > i) & 1, and the all-visited target (1 << n) - 1. Iterating masks in increasing numeric order also reaches every subset after all of its own subsets, which lets the DP be written as plain nested loops.

Bitmask DP

Bitmask DP is dynamic programming that encodes subsets or assignments as bitmasks, which makes problems solvable when N is small (up to 20).

A cell here says: these cities have been visited, and I am standing at this one. What it deliberately forgets is the ORDER they were visited in — which is the whole saving, because two routes covering the same set and ending in the same place are interchangeable from here on, so only the cheaper one is worth keeping. Watch what that costs: most of the table cannot exist, and at this size the DP prices more transitions than brute force prices tours.

BASE

Set

0001

0011

∞

0101

∞

1001

∞

0111

∞

1011

∞

1101

∞

1111

∞

Row 0011 is the set {0, 1} — bits read right to left, so city 0 is the last digit.

Filled

1/13

Checks

0/15

Best

—

Every route starts the same way, so the table starts with one cell: dp[{0}][0] = 0 — city 0 visited, standing on it, nothing spent. A cell here reads "these cities have been visited and I am at this one", which is why only 13 of the 64 cells can ever hold anything: the city stood at has to be one of the visited ones, the set has to include the start, and the city stood at can never BE the start — a route leaves city 0 once and does not stand on it again until the tour closes. The rest of the table is not empty, it is impossible.

{0} covered, standing at 0, for 0. Take the road to 1 — it costs 10 — and that is 0 + 10 = 10 to cover {0, 1} ending at 1. That cell was ∞ — nothing had reached it yet — so it becomes 10. One number now stands for every route that covers {0, 1} and ends at 1, whatever order it took to get there.

13 of the 64 cells can ever hold a value. 15 transitions against 6 brute-force tours.

Road costs

Order: 0-1, 0-2, 0-3, 1-2, 1-3, 2-3 — 3 costs make 3 cities, 6 make 4, 10 make 5.

Intuition

The Restriction: Standard DP arrays work well when states are indices (e.g., dp[i]). But what if the state is a set of visited cities or available jobs?

The Solution: Use an integer as a bitmask to represent a set. If the j-th bit is set (1), element j is present/visited.

Since an integer can store up to 30-60 bits, we can represent any subset of size N efficiently if N <= 20.

Concept

Bit Operations Recap:

Set bit i: mask | (1 << i)
Check bit i: (mask >> i) & 1
Toggle bit i: mask ^ (1 << i)
All bits set: (1 << N) - 1

State Definition: Usually dp[mask][current_element], where mask represents the set of visited elements and current_element is the last added item.

How it Works

Definite State: Identify what needs to be tracked. Usually "what elements are used" (mask) and "where are we now" (index).
Transitions: Iterate through all subsets (masks) and try adding an available element (unvisited bit).
Base Cases: dp[0][...] or dp[1 << start_node][start_node] usually initialized to 0 or cost.

Step-by-Step Breakdown

1. Initialize: Create a DP table of size 2^N * N. Fill with infinity or appropriate default.
2. Base Case: Set starting masks (e.g., visiting the first city).
3. Iterate: Loop through mask from 1 to 2^N - 1.
4. Inner Loop: Loop through u (current node) and v (next node).
5. Update: If u is in mask and v not in mask, update dp[mask | (1<<v)][v].

When to Use

Problems involving permutations or subsets where N is small (N <= 20).
Traveling Salesman Problem (TSP).
Assignment Problems (Assign N jobs to N people).
Hamiltonian Path/Cycle problems.

When NOT to Use

When N > 20 (Space/Time 2^N becomes too large).
When the problem can be solved greedily or using standard flow algorithms.

How to Identify

"Find shortest path visiting all nodes", "Assign N tasks to N workers with min cost", Constraints: N <= 20.

AI resume checker — match your resume to the job description

Suffix Array

Matrix Exponentiation

Complexity

Time (Best)

O(N * 2^N)

Time (Average)

O(N^2 * 2^N)

Time (Worst)

O(N^2 * 2^N)

Space

O(N * 2^N)

Bitmask DP Code

1function tsp(dist) {
2    const n = dist.length;
3    const VISITED_ALL = (1 << n) - 1;
4    const dp = Array.from({ length: 1 << n }, () => new Array(n).fill(Infinity));
5    
6    dp[1][0] = 0;
7    
8    for (let mask = 1; mask < (1 << n); mask++) {
9        for (let i = 0; i < n; i++) {
10            if ((mask >> i) & 1) {
11                for (let j = 0; j < n; j++) {
12                    if (!((mask >> j) & 1)) {
13                        let nextMask = mask | (1 << j);
14                        dp[nextMask][j] = Math.min(dp[nextMask][j], dp[mask][i] + dist[i][j]);
15                    }
16                }
17            }
18        }
19    }
20    
21    let ans = Infinity;
22    for (let i = 1; i < n; i++) {
23        ans = Math.min(ans, dp[VISITED_ALL][i] + dist[i][0]);
24    }
25    return ans;
26}

Related Lessons

Bitmask DP

Intuition

Concept

How it Works

Step-by-Step Breakdown

When to Use

When NOT to Use

How to Identify

Sample Problems

Smallest Sufficient Team

Partition to K Equal Sum Subsets

Shortest Path Visiting All Nodes

AI resume checker — match your resume to the job description

Introduction

Introduction

Heap Operations

Heap Sort

Frequently Asked Questions

Why is N limited to around 20?

What does the mask represent?

Which bit operations do I need?