Bitmask DP

Bitmask DP represents a set of chosen or visited items as bits in an integer.

It is useful when the state must remember which items from a small collection have already been used.

Core Idea

If there are n items, a mask from 0 to 2 ** n - 1 can represent any subset. Bit i is 1 when item i is included.

The number of masks grows exponentially, so this technique is usually for relatively small n.

Function Contracts

contains(mask, i) expects an integer mask and a bit position i. It returns whether item i is included.

add_item(mask, i) returns a new mask with item i included. These helpers assume items are numbered from 0 upward.

Python Example

def contains(mask, i):
    return (mask & (1 << i)) != 0
 
 
def add_item(mask, i):
    return mask | (1 << i)

These operations test and add items using bit positions.

DP State Example

A traveling-salesman-like state can be:

dp[mask][last] = minimum cost to visit the set mask and end at last

Here mask records which nodes have already been visited, and last records the current position. Both pieces are necessary because future moves depend on both.

Step-by-Step Mask Meaning

If n = 4, the mask 0b1011 means items 0, 1, and 3 are included. Item 2 is not included.

Testing item 2:

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

returns False.

Complexity

There are 2 ** n possible masks. If each mask also tracks a last position, the number of states may be O(n * 2^n). This grows quickly.

How To Recognize It

Bitmask DP is a candidate when the problem says or implies “which items have already been used?” and the number of items is small, often around 20 or less depending on transitions.

If the state needs an unordered subset, a bitmask can be a compact key for that subset.

Failure Example

If n = 30, then 2 ** n is already more than one billion possible masks. A bitmask representation is compact, but it does not remove the exponential number of subsets.

Bitmask DP is practical only when the item count is small enough for the state count and transitions.

Common Confusions

Bitmask DP is not faster because bits are magical. It is useful because it gives a compact way to store subset state.

The number of states can still be huge. 2 ** 20 is already more than one million masks.

Another common mistake is using bitmask DP when n is too large. The compact representation does not remove exponential growth.

When To Use It

Use bitmask DP for subset selection, visiting all nodes in a small graph, assignment problems, and traveling-salesman-like states.

Do not use it for large sets unless additional structure reduces the state space.

The Main Point

Bitmask DP stores subset state compactly, but the number of subsets is still exponential.