Bitmask DP Interview Questions: Subset States and Assignment Problems

Bitmask DP interview questions ask whether many different decision orders can be collapsed into the same future state. In a worker-to-job assignment, a mask records which jobs are taken; the number of assigned workers is popcount(mask). If the cost of assigning the next worker depends only on that worker and the chosen job, every history that reaches the same mask has the same possible future. That is the reason dynamic programming works—not the bit operators themselves.

The record is a related exercise, not a prediction of your interview. The minimum-cost matrix below is an original example; the official AtCoder Matching task supplies a separate counting formulation.

When is a mask a sufficient state?

Suppose there are n workers and n jobs. Every worker gets one distinct job. Process workers in fixed order. A mask of n bits has bit j set if job j has already been assigned. At state mask, worker i = popcount(mask) is next. For every unused compatible job j, transition to mask | (1 << j) and add that assignment's cost.

The fixed worker order is load-bearing. If workers could be chosen in arbitrary order and their identity affected future costs, the chosen-jobs mask alone would not tell you which worker is next. Similarly, if cost depends on the previous job, two orders reaching the same set could have different future costs. Then add the missing information, such as lastJob, to the state. State sufficiency is a proof obligation: equal state must imply equal future choices and incremental costs.

Ask for n before writing code. 2^n states are attractive when n is small, but a mask does not make an exponential algorithm polynomial. Also ask whether the task wants feasibility, number of matchings, minimum cost, maximum score, or one reconstructed assignment. The state may be identical while initialization, combination, and impossible-value handling change.

Work a four-by-four minimum-cost assignment

Let workers be A, B, C, D and jobs be 0, 1, 2, 3. Entries are costs. A dash is forbidden; worker A cannot take job 3, and worker C cannot take job 1.

Worker	Job 0	Job 1	Job 2	Job 3
A	4	1	3	—
B	2	0	5	8
C	3	—	2	5
D	7	6	4	1

Define dp[mask] as the smallest cost to assign the first popcount(mask) workers to exactly the jobs in mask. Set dp[0]=0 and all other entries to infinity. For each reachable mask, let i=popcount(mask), then relax each unused allowed job j:

next = mask | (1 << j)
dp[next] = min(dp[next], dp[mask] + cost[i][j])

At the empty mask, assign A to job 0 for cost 4, job 1 for cost 1, or job 2 for cost 3. If A takes job 1 (0010 with bit 0 on the right), B can take job 0, producing 0011 at cost 1+2=3. Then C takes job 2, producing 0111 at cost 5, and D takes job 3, producing 1111 at cost 6. The resulting assignment (1,0,2,3) is optimal for this fixture; an exhaustive enumeration of all 24 permutations, excluding forbidden edges, found 14 valid assignments and minimum cost 6.

Do not mistake this trace for a greedy algorithm. Other partial states can reach the same mask with different costs; keep only the cheaper one because all future choices from that mask are identical under the stated cost model. To reconstruct an answer, store a predecessor mask and chosen job whenever a relaxation improves dp[next], then walk backward from the full mask. If ties need a particular order, encode that policy explicitly rather than relying on iteration order.

Implement the transition carefully

A concise Python 3.10+ solution makes impossible states visible; it uses int.bit_count(), which is unavailable in older Python versions. It handles n=0 as a zero-cost empty assignment, represents forbidden cells with None, and returns None if no complete assignment exists.

def min_assignment(cost):
    n = len(cost)
    if any(len(row) != n for row in cost):
        raise ValueError("cost must be square")
    full = 1 << n
    inf = float("inf")
    dp = [inf] * full
    parent = [None] * full
    dp[0] = 0

    for mask in range(full):
        if dp[mask] == inf:
            continue
        worker = mask.bit_count()
        if worker == n:
            continue
        for job in range(n):
            if mask & (1 << job) or cost[worker][job] is None:
                continue
            nxt = mask | (1 << job)
            candidate = dp[mask] + cost[worker][job]
            if candidate < dp[nxt]:
                dp[nxt] = candidate
                parent[nxt] = (mask, job)

    if dp[full - 1] == inf:
        return None
    jobs = [None] * n
    mask = full - 1
    while mask:
        previous, job = parent[mask]
        jobs[previous.bit_count()] = job
        mask = previous
    return dp[full - 1], jobs

Each of 2^n masks considers up to n jobs, so time is O(n·2^n) and space is O(2^n). The number of valid transition attempts is at most n·2^(n-1) because each bit is unset in half of the masks, though forbidden edges and unreachable states reduce actual work. The parent array is for reconstruction; remove it if only the cost is required.

None is better than a magic negative number for forbidden cost entries when legitimate costs can be negative. With negative costs, the DAG order still works because every transition increases the number of set bits; there are no cycles. Do not conflate this with shortest paths on an arbitrary negative-weight graph.

Turn the same state into a counting DP

The AtCoder DP O Matching problem asks for the number of perfect matchings under a compatibility matrix, modulo 1,000,000,007; its stated bound is n <= 21. Use ways[0]=1 and add contributions instead of taking a minimum:

ways[mask | (1 << j)] += ways[mask]

Apply the modulus after each addition. The worker index remains popcount(mask). Each complete worker-to-job assignment follows exactly one path through fixed worker order, so no assignment is counted twice. If a row has no compatible unused job, that state contributes zero to later masks.

This is an important interview distinction: for minimum cost, two histories at the same mask collapse to the better one; for counting, their counts must be summed. If the task wants both number of valid assignments and best score, maintain separate aggregates with their own combination rules.

Prove the state and recurrence in two sentences

Induct on popcount(mask). At mask=0, the empty assignment of zero workers has cost zero and there is one empty way. Assume the DP value for each mask represents the correct aggregate over assignments of the first i workers to exactly that job set. Every legal complete assignment of i+1 workers has a unique last job j assigned to worker i; removing it yields a predecessor mask of size i. The transition includes all and only those legal assignments, so min or sum computes the intended aggregate.

That proof also reveals what breaks if workers are not fixed in order: the same predecessor mask could describe different workers already assigned. popcount(mask) would no longer identify the next worker, and the recurrence would omit necessary history.

Know when bitmask DP is the wrong tool

If n is too large, O(n·2^n) time and O(2^n) memory may be impossible. For minimum-cost unrestricted assignment, a polynomial-time assignment algorithm may be more appropriate. For sparse compatibility or small alternative dimensions, a different state orientation can help. State the complexity budget rather than saying “bitmask DP is fast.”

If costs depend on the order of jobs, such as a setup cost from the previous job, use dp[mask][last]. If a worker can take multiple jobs, popcount(mask) no longer counts assigned workers. If the objective includes resources beyond the selected set, add the resource to the state or prove it is derivable. The goal is not to force a mask into every combinatorial problem; it is to compress exactly the history future decisions cannot distinguish.

The mask can also represent different universes: chosen branches in an order-optimization problem, available hats, or letters already used. Before copying a transition, state what bit j=1 means. A compatibility test such as (mask & itemMask)==0 is a set-disjointness rule, not necessarily an assignment DP recurrence.

Verify with permutations and boundary cases

For this four-worker matrix, the simplest oracle enumerates permutations of jobs, rejects forbidden worker-job pairs, and computes each remaining total. It confirmed 14 valid permutations and minimum 6. Compare the DP result and reconstructed job list with that oracle on random matrices of size at most 7. This catches both recurrence mistakes and parent reconstruction bugs.

Test n=0, one allowed cell, one forbidden cell, no perfect matching, all cells allowed, negative costs, and ties. For the counting variant, all-compatible n=3 should yield 3!=6; one forced diagonal should yield one. For minimum cost, verify that the reconstructed assignment uses every job once and its summed cost equals the reported DP value. If it does not, a correct numeric optimum may be hiding a broken parent pointer.

What to say at the whiteboard

“I process workers in a fixed order. The mask records exactly which jobs are used, so its popcount identifies the next worker. Every legal unused job creates a larger mask. Two histories at the same mask have identical future options, so I keep their minimum cost—or sum their counts if that is the objective. The DP has 2^n states and up to n transitions per state. I will compare small cases with exhaustive permutations.”

That answer explains the compression, recurrence, complexity, and validation. Practice the hat-assignment exercise and then ask whether its count and score can share one aggregate. The moment you articulate why they cannot, you have moved beyond memorizing a mask template.

Sources and Further Reading

• AtCoder Educational DP Contest O: Matching

The cost matrix was enumerated locally; it is an original practice fixture.