Bitmask DP: Dynamic Programming with Bitmasks

Bitmask DP is used when n is small and the problem asks you to choose, assign, match, or visit elements.

Each bit represents whether an element has been chosen.

The mask-as-state idea from TSP — one integer remembers the whole visit set:

Bitmask DP (TSP Intuition)

Use a bitmask to represent 'which cities visited' in a DP state.

State = (mask, last) where mask bit i means city i visited. Every subset of cities has exactly one integer, so the DP table is 2ⁿ·n states. Transitions only consider cities NOT in the mask, so the 'no repeats' constraint is free. O(2ⁿ·n²) beats n! brute force for small n.

ARRAY VISUALIZER

Steps –

city0

city1

city2

city3

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        # dp[mask][last] = min cost visiting set 'mask', ending at 'last'
                      
                        2
                        for mask in 1 .. (1<<n)-1:
                      
                        3
                          for last in mask:
                      
                        4
                            for next NOT in mask:
                      
                        5
                              dp[mask|1<<next][next] = min(
                      
                        6
                                …, dp[mask][last] + dist[last][next])

Recognition Cheat Sheet

If you see…	Think…
`n <= 20` and choose subsets	Bitmask DP
Assign items to people	Bitmask DP
Visit all nodes	Bitmask DP
Match / pair elements	Bitmask DP
Minimum cost using each element once	Bitmask DP
Subset optimization	Bitmask DP

Main Trigger

Small n + subsets/assignment/visit all + DP → Think Bitmask DP

1. The Basic Idea

A number represents which elements have been selected.

mask = 0000 → nothing selected
mask = 0101 → elements 0 and 2 selected
mask = 1111 → all elements selected

For element i:

(mask & (1 << i)) != 0

means element i is already selected.

To add element i:

mask | (1 << i)

2. Generic Java Template

int[] dp = new int[1 << n];
Arrays.fill(dp, Integer.MAX_VALUE);

dp[0] = 0;

for (int mask = 0; mask < (1 << n); mask++) {
    if (dp[mask] == Integer.MAX_VALUE) continue;

    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) continue;

        int newMask = mask | (1 << i);

        dp[newMask] = Math.min(
            dp[newMask],
            dp[mask] + cost(i)
        );
    }
}

dp = [float('inf')] * (1 << n)

dp[0] = 0

for mask in range(1 << n):
    if dp[mask] == float('inf'):
        continue

    for i in range(n):
        if mask & (1 << i):
            continue

        new_mask = mask | (1 << i)

        dp[new_mask] = min(
            dp[new_mask],
            dp[mask] + cost(i)
        )

vector<int> dp(1 << n, INT_MAX);

dp[0] = 0;

for (int mask = 0; mask < (1 << n); mask++) {
    if (dp[mask] == INT_MAX) continue;

    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) continue;

        int newMask = mask | (1 << i);

        dp[newMask] = min(
            dp[newMask],
            dp[mask] + cost(i)
        );
    }
}

const dp = new Array(1 << n).fill(Infinity);

dp[0] = 0;

for (let mask = 0; mask < (1 << n); mask++) {
  if (dp[mask] === Infinity) continue;

  for (let i = 0; i < n; i++) {
    if ((mask & (1 << i)) !== 0) continue;

    const newMask = mask | (1 << i);

    dp[newMask] = Math.min(
      dp[newMask],
      dp[mask] + cost(i)
    );
  }
}

The pattern is:

Current subset
      ↓
Choose unused element
      ↓
Add element to mask
      ↓
Update DP

3. Top-Down Template

Sometimes recursion + memoization is easier:

int[] dp;

int solve(int mask) {
    if (mask == (1 << n) - 1)
        return 0;

    if (dp[mask] != -1)
        return dp[mask];

    int ans = Integer.MAX_VALUE;

    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0)
            continue;

        int newMask = mask | (1 << i);

        ans = Math.min(
            ans,
            cost(i) + solve(newMask)
        );
    }

    return dp[mask] = ans;
}

dp = [-1] * (1 << n)

def solve(mask):
    if mask == (1 << n) - 1:
        return 0

    if dp[mask] != -1:
        return dp[mask]

    ans = float('inf')

    for i in range(n):
        if mask & (1 << i):
            continue

        new_mask = mask | (1 << i)

        ans = min(
            ans,
            cost(i) + solve(new_mask)
        )

    dp[mask] = ans
    return ans

vector<int> dp;

int solve(int mask) {
    if (mask == (1 << n) - 1)
        return 0;

    if (dp[mask] != -1)
        return dp[mask];

    int ans = INT_MAX;

    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0)
            continue;

        int newMask = mask | (1 << i);

        ans = min(
            ans,
            cost(i) + solve(newMask)
        );
    }

    return dp[mask] = ans;
}

const dp = new Array(1 << n).fill(-1);

function solve(mask) {
  if (mask === (1 << n) - 1)
    return 0;

  if (dp[mask] !== -1)
    return dp[mask];

  let ans = Infinity;

  for (let i = 0; i < n; i++) {
    if ((mask & (1 << i)) !== 0)
      continue;

    const newMask = mask | (1 << i);

    ans = Math.min(
      ans,
      cost(i) + solve(newMask)
    );
  }

  return (dp[mask] = ans);
}

Key State

dp[mask]

means:

Best answer after selecting the elements represented by mask.

4. Assignment / Matching

Example:

Assign each worker one job with minimum total cost.

int[] dp = new int[1 << n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;

for (int mask = 0; mask < (1 << n); mask++) {
    int worker = Integer.bitCount(mask);

    for (int job = 0; job < n; job++) {
        if ((mask & (1 << job)) != 0)
            continue;

        int next = mask | (1 << job);

        dp[next] = Math.min(
            dp[next],
            dp[mask] + cost[worker][job]
        );
    }
}

dp = [float('inf')] * (1 << n)
dp[0] = 0

for mask in range(1 << n):
    worker = bin(mask).count('1')

    for job in range(n):
        if mask & (1 << job):
            continue

        nxt = mask | (1 << job)

        dp[nxt] = min(
            dp[nxt],
            dp[mask] + cost[worker][job]
        )

vector<int> dp(1 << n, INT_MAX);
dp[0] = 0;

for (int mask = 0; mask < (1 << n); mask++) {
    int worker = __builtin_popcount(mask);

    for (int job = 0; job < n; job++) {
        if ((mask & (1 << job)) != 0)
            continue;

        int next = mask | (1 << job);

        dp[next] = min(
            dp[next],
            dp[mask] + cost[worker][job]
        );
    }
}

const bitCount = (x) => x.toString(2).replaceAll('0', '').length;

const dp = new Array(1 << n).fill(Infinity);
dp[0] = 0;

for (let mask = 0; mask < (1 << n); mask++) {
  const worker = bitCount(mask);

  for (let job = 0; job < n; job++) {
    if ((mask & (1 << job)) !== 0)
      continue;

    const next = mask | (1 << job);

    dp[next] = Math.min(
      dp[next],
      dp[mask] + cost[worker][job]
    );
  }
}

Recognition

Assign each item exactly once + small n → Bitmask DP

5. Visit All Nodes

Common in:

Traveling Salesman
Visit every city
Shortest path visiting all nodes

The state often becomes:

dp[mask][last]

Meaning:

Minimum cost after visiting the nodes in mask and currently standing at last.

Transition:

for (int next = 0; next < n; next++) {
    if ((mask & (1 << next)) != 0)
        continue;

    int newMask = mask | (1 << next);

    dp[newMask][next] =
        Math.min(
            dp[newMask][next],
            dp[mask][last] + graph[last][next]
        );
}

Recognition

Visit all nodes + track current position → dp[mask][last]

6. Partition / Subset Problems

Bitmask can also represent a chosen group:

int mask = 0;

for (int i = 0; i < n; i++) {
    if ((mask & (1 << i)) != 0) {
        // i belongs to this subset
    }
}

Useful for:

Partition into groups
Choose a subset
Equal-sum groups
Subset optimization
Pairing elements

Common Mistakes

1. Using Bitmask DP for large `n`

The number of states is:

2^n

So it is usually practical only when n is small, commonly around 20–22 or less, depending on the transition cost.

2. Wrong bit check

Already selected:

(mask & (1 << i)) != 0

Not selected:

(mask & (1 << i)) == 0

3. Forgetting to create the new mask

int newMask = mask | (1 << i);

Don’t modify the current state.

4. Wrong DP state

Ask:

What information about my choices is needed to continue?

Often:

dp[mask]

or:

dp[mask][last]

Pattern Evolution

Subset representation
        ↓
dp[mask]
        ↓
Assignment / Matching
        ↓
dp[mask]
        ↓
Visit all nodes
        ↓
dp[mask][last]

Java Bit Operations You Should Know

// Is i selected?
(mask & (1 << i)) != 0

// Add i
mask | (1 << i)

// Remove i
mask & ~(1 << i)

// Toggle i
mask ^ (1 << i)

// Number of selected elements
Integer.bitCount(mask)

// All elements selected
mask == (1 << n) - 1

# Is i selected?
(mask & (1 << i)) != 0

# Add i
mask | (1 << i)

# Remove i
mask & ~(1 << i)

# Toggle i
mask ^ (1 << i)

# Number of selected elements
bin(mask).count('1')

# All elements selected
mask == (1 << n) - 1

// Is i selected?
(mask & (1 << i)) != 0

// Add i
mask | (1 << i)

// Remove i
mask & ~(1 << i)

// Toggle i
mask ^ (1 << i)

// Number of selected elements
__builtin_popcount(mask)

// All elements selected
mask == (1 << n) - 1

// Is i selected?
(mask & (1 << i)) !== 0

// Add i
mask | (1 << i)

// Remove i
mask & ~(1 << i)

// Toggle i
mask ^ (1 << i)

// Number of selected elements
mask.toString(2).replaceAll('0', '').length

// All elements selected
mask === (1 << n) - 1

Complexity

There are:

2^n

possible subsets.

If we try all n elements from every subset:

Time:  O(n * 2^n)
Space: O(2^n)

For dp[mask][last], space can become:

O(n * 2^n)

Interview Rule

Small n + choose/assign/match/visit elements exactly once → Think Bitmask DP.

The key idea is simple:

Bit = chosen / not chosen
        ↓
Mask = current subset
        ↓
DP = best answer for that subset
        ↓
Add one unused element

⚠️ Animation & Content Notice

Bit DP

⚠️ Animation & Content Notice

Bitmask DP (TSP Intuition)

Recognition Cheat Sheet

Main Trigger

1. The Basic Idea

2. Generic Java Template

3. Top-Down Template

Key State

4. Assignment / Matching

Recognition

5. Visit All Nodes

Recognition

6. Partition / Subset Problems

Common Mistakes

1. Using Bitmask DP for large `n`

2. Wrong bit check

3. Forgetting to create the new mask

4. Wrong DP state

Pattern Evolution

Java Bit Operations You Should Know

Complexity

Interview Rule

Premium Content

My Private Notes

Earn Premium with Referrals

Bitmask DP (TSP Intuition)

Recognition Cheat Sheet

Main Trigger

1. The Basic Idea

2. Generic Java Template

3. Top-Down Template

Key State

4. Assignment / Matching

Recognition

5. Visit All Nodes

Recognition

6. Partition / Subset Problems

Common Mistakes

1. Using Bitmask DP for large n

2. Wrong bit check

3. Forgetting to create the new mask

4. Wrong DP state

Pattern Evolution

Java Bit Operations You Should Know

Complexity

Interview Rule

Premium Content

My Private Notes

1. Using Bitmask DP for large `n`