Bitmask DP applies when the DP state involves a subset of elements. Instead of storing sets explicitly, the subset is encoded as a binary integer, which makes the state a plain number between 0 and 2^n - 1. Problems like "assign n people to n tasks" or "visit all n cities" become DPs over these integer-encoded subsets.

It only works when n is small (typically n <= 20), because the number of subsets grows exponentially. When the constraint fits, bitmask DP turns an exponential brute force over orderings into a polynomial sweep over subsets.

Consider a set of 4 elements: {A, B, C, D}. Each element is either included or not, which we can represent with a bit. The bitmask 1011 (which equals 11 in decimal) means elements at indices 0, 1, and 3 are included, while element 2 is not.

Every subset maps to exactly one integer between 0 and 2^n - 1. The bitmask compresses a subset into a single number, and that number becomes the DP state.

The following diagram shows the subset lattice for n = 3 elements {a, b, c}. Each node is a bitmask, and edges connect subsets that differ by exactly one element.

Each level represents subsets of a particular size. The DP transitions move upward through this lattice, building larger subsets from smaller ones.

The following bit operations appear throughout bitmask DP solutions.

The common transition pattern iterates over elements and tries to add each unused one to the current subset:

Two signals matter: small n (typically n <= 20, sometimes n <= 15) and subset selection (choosing, assigning, or visiting elements). When both are present, bitmask DP is a candidate. The problem families that fit:

The constraint to look for is n <= 20. If n can be up to 1000, bitmask DP does not apply because 2^1000 states are far too many. But 2^20 is about one million, which is manageable.

A second signal is when the problem asks to track "which elements have been used." A boolean visited array carried across recursive calls can usually be replaced with a bitmask.

The general framework for bitmask DP is:

The time complexity is *O(2^n n) in most cases: there are 2^n possible masks, and for each mask you iterate over n elements. The space complexity is O(2^n)** for the DP table.

Each transition adds one element, moving upward through the subset lattice shown earlier. It is structurally a BFS through subsets, where each level adds one more element.

Problem Statement

Given an integer array nums and an integer k, return true if it is possible to divide the array into k non-empty subsets whose sums are all equal.

Example: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 Total sum = 20, target sum per subset = 20 / 4 = 5. One valid partition: {5}, {4, 1}, {3, 2}, {3, 2}. Return true.

Constraints: 1 <= k <= nums.length <= 16

The constraint n <= 16 enables a bitmask DP solution (2^16 = 65536 states).

Intuition

The brute force tries every way to partition n elements into k groups, giving k^n combinations. The problem can be reframed.

Instead of asking "which group does each element go to," process elements one by one, adding each to the current bucket. When a bucket reaches the target sum, start a new bucket.

Define dp[mask] = the current sum within the bucket being filled, given that the elements indicated by mask have already been placed. When the sum reaches target, the bucket closes and the value resets to 0 (stored as sum_of_used_elements % target). If dp[mask] + nums[i] would exceed the target, element i is skipped for this bucket.

The answer is true if dp[(1 << n) - 1] is well-defined (every element was placed).

Step-by-Step Trace

Trace a few key transitions with nums = [4, 3, 2, 3, 5, 2, 1], k = 4, target = 5.

The value -1 means "this state is unreachable."

Every time the current bucket sum hits the target, the value resets to 0. Reaching the full mask with a non-negative dp value means every element was placed into a bucket of exactly target sum.

Implementation

Complexity Analysis

K-Subsets used dp[mask] with a single dimension. The Travelling Salesman Problem (TSP) is the canonical bitmask DP, and it needs a second dimension. The reason it needs one explains the general rule for choosing the state shape.

Problem Statement

Given an n x n matrix dist[i][j] representing the cost of travelling from city i to city j, find the minimum-cost tour that starts at city 0, visits every city exactly once, and returns to city 0. Typical interview constraint: n <= 20.

Why dp[mask] Is Not Enough

In K-Subsets, the value stored at a state (current bucket sum) depended only on which elements had been placed, not on the order. Two execution paths that arrived at the same mask with the same bucket sum were interchangeable.

TSP is different. The cost of extending a partial tour depends on which city you are currently at. Two paths that have visited the exact same set of cities can be sitting at different last cities, and the cheapest next edge depends on which one. A single-dimensional dp[mask] cannot distinguish those situations.

The fix is to add the current position to the state:

Recurrence

To be at (mask, i), the previous step must have been at some city j that is also in mask, with j != i, and the predecessor mask must be mask with bit i cleared. The transition:

dp[mask][i] = min over j in mask, j != i of ( dp[mask ^ (1 << i)][j] + dist[j][i] )

Implementation

Complexity Analysis

The General Rule

The state needs whatever the future cost depends on. K-Subsets only cared about the running bucket sum, which is a function of mask alone. TSP cares about the running cost plus the current city, because the next edge cost depends on it. The same rule appears in:

If the answer at a partial state depends on something more than "what's been used," that something belongs in the state. The shape of the bitmask DP follows from this requirement, not from the bitmask itself.

K-Subsets and TSP both transition by adding one element at a time: mask -> mask | (1 << i). A different family of bitmask problems transitions by partitioning a mask into two submasks: pick a subset sub of mask, do something with sub and mask ^ sub separately, then combine. The classic example is Set Cover and any partition-style DP.

The transition needs to iterate over every subset of mask (not every subset of {0, ..., n - 1}). The standard idiom for this is the submask enumeration trick:

Why The Idiom Works

The expression (sub - 1) & mask produces the next smaller submask of mask, in strictly decreasing order. Two ideas combine:

Starting from sub = mask, the iteration visits every submask of mask in decreasing order and stops just before sub = 0. The loop guard sub > 0 is correct: the loop body runs for every non-zero submask, and the post-condition sub = (sub - 1) & mask happens to compute mask itself when sub = 0, which would cause infinite recursion if the loop did not exit first. If the algorithm requires the sub = 0 case (the empty subset), handle it before or after the loop.

Why The Total Cost Is O(3^n), Not O(4^n)

A naive analysis says: there are 2^n possible masks, each with up to 2^n possible submasks, so the total work is 2^n * 2^n = 4^n. The actual bound is tighter: O(3^n).

The reason: instead of counting (mask, sub) pairs by mask, count them by the bit. Each bit can be in one of three states across the pair:

(The case "in sub but not in mask" cannot occur because sub is a submask of mask.)

So the total number of valid (mask, sub) pairs is 3^n. The submask enumeration idiom visits exactly these pairs and no others. For n = 16, 3^16 is about 43 million, still feasible; 4^16 would be 4 billion, infeasible.

Worked Example: Smallest Sufficient Team (LC 1125)

You are given req_skills, a list of skills (size m, up to 16), and people, a list of skill sets each person has. Return the indices of a smallest subset of people whose combined skill set covers all req_skills.

Treat each req_skills as a bit position. Each person's skill set is a bitmask peopleMask[i]. The DP state is dp[mask] = the indices of a smallest team whose combined skills are exactly mask. The transition: for each person p, dp[mask | peopleMask[p]] can be reached from dp[mask] by adding p.

For the smaller, partition-style variant ("split the required skills into two halves and solve each independently"), submask enumeration is the natural fit:

For LC 1125 specifically, the forward "add one person at a time" formulation is simpler and faster, but split-based variants (especially when subproblems have a known structure) need the submask enumeration.

When To Reach For Submask Enumeration

Use it when the recurrence at state mask reads from dp[sub] and dp[mask ^ sub] for some submask sub, not just from dp[mask without one element]. This shows up in:

For the simpler "add one element" recurrences, the standard nested loop for (int i = 0; i < n; i++) if (!(mask & (1 << i))) is enough and cheaper. The submask idiom is a tool you reach for only when the recurrence demands it.