Imagine you're running a small team. Three people, three tasks, and a grid of costs — how much time each person needs for each task. The cheapest assignment isn't obvious because every choice constrains the remaining ones. Assign Alice to the fast task and maybe Bob gets stuck with an expensive one. The problem isn't any single assignment; it's finding the combination that minimizes the total.

This is the assignment problem, and it shows up everywhere: scheduling shifts, routing deliveries, pairing resources to jobs. For 3 people the cost grid is small — you could eyeball it. But the structure hides a trap. Each valid assignment is a permutation: a one-to-one mapping of people to tasks. With 3 people, there are 3! = 6 permutations. With 10 people, there are 3,628,800. With 15? Over a trillion.

The only way to guarantee the optimum is to check every permutation. Try it below — build two assignments by hand and feel how quickly even the small case becomes tedious.

You just experienced the brute-force approach: pick a person, assign them a task, pick the next person, assign them a different task, repeat. Every distinct sequence of assignments is one permutation. For 3 people, those permutations form a tree — the root branches into 3 first-task choices, each of those branches into 2 remaining choices, and the leaves are the 6 complete assignments.

The tree is small here, but its shape is the problem. Each level multiplies the branch count by one fewer option: 3 x 2 x 1 = 6. For n people, the tree has n! leaves. That multiplicative branching is why factorial growth is so devastating — it doesn't just grow fast, it multiplies the previous size at every step.

Two of those permutations are already built. Construct the third one yourself and watch how the “used items” state evolves with each assignment.

Three permutations, three different orderings. Each one made different choices — but are the intermediate states really that different? Look at the steps side by side and pay attention to what information actually matters for the remaining decisions.

Something interesting is hiding in those intermediate states. Two different permutations, two different sequences of assignments — but at certain points, they end up in functionally identical positions. Can you spot what they share, and why it means the remaining work is identical?

Find the pair of steps below that share an identical state. What does that shared state tell you about the search space?

The structure below is a Hasse diagram — a lattice where each node represents a subset of tasks, and edges connect subsets that differ by exactly one element. The bottom node is the empty set {} (no tasks assigned, cost 0). The top node is the full set {0, 1, 2} (all three tasks assigned). Each level of the lattice corresponds to a number of tasks: level 1 has the three singletons {0}, {1}, {2}, level 2 has the three pairs, and level 3 is the full set.

Each node's optimal cost has to come from somewhere. Look at the edges connecting subsets — they represent adding exactly one task. If you're standing at a node, which other nodes could you have come from? And if you know the costs of those predecessor nodes, how would you compute the cost of the current one?

Fill each node with its optimal cost, starting from the bottom. The lattice structure will guide you — but figuring out the rule for combining costs is the real challenge.

You filled the 3-task lattice by hand: 8 nodes, a manageable diamond. Now add one more task. The lattice doubles — 16 nodes instead of 8, five layers instead of four. That's the cost of one extra bit in the bitmask.

Each additional task doubles the number of subsets because each existing subset either includes or excludes the new task. A 3-bit mask has 2^3 = 8 states. A 4-bit mask: 2^4 = 16. A 15-bit mask: 2^15 = 32,768. This exponential growth sounds scary, but compare it to 15! = 1.3 trillion — the bitmask representation compresses the search space by a factor of millions.

Fill the critical path through the 4-task lattice to see the pattern hold at larger scale.

You filled the lattice by hand. Now assemble the formula that does it for you. The recurrence has four moving parts: the current state (which tasks are assigned), the previous state (one fewer task), the transition cost (assigning a specific person to a specific task), and the minimization over all valid last-task choices.

The formula has to capture the same reasoning you used when filling the lattice by hand. You know the ingredients — a mask representing assigned tasks, a way to step backward to a smaller subset, a cost to add, and a way to pick the best option. But how do those pieces fit together symbolically?

Build the formula from tiles below. Start with the predecessor expression — how do you step from a mask to the state before the last task was assigned? — then assemble the full recurrence.

Every lattice edge maps to a line of TypeScript. The outer loop iterates masks in ascending order (guaranteeing smaller subsets are filled first). The inner loop iterates set bits of the current mask. The XOR clears one bit to step down the lattice. The cost lookup uses popcount(mask) - 1 as the person index.

This correspondence — visual lattice edge to code line — is the code bridge. Understanding it means you can write the implementation from the diagram, or read an implementation and see the diagram it traverses.

Find the connections, then fill the blanks.

function assignDP(cost: number[][], n: number) {

  const dp = new Array(___).fill(Infinity)

  dp[0] = 0

  for (let mask = 1; mask < (1 << n); mask++) {

    const pc = popcount(mask)

    for (let j = 0; j < n; j++) {

      if (___) {

        const prev = ___

        dp[mask] = Math.min(dp[mask], prev + cost[pc-1][j])

      }

    }

  }

  return dp[(1 << n) - 1]

}

Remember the explosion counter from the first screen? That was factorial growth: 15! permutations, a number so large it overflowed the container and shook the screen. Now watch the bitmask DP counter.

The difference isn't incremental — it's categorical. Factorial grows by multiplying at each step. Exponential grows by doubling. For small n the gap is negligible, but by n = 10 factorial is already 354 times larger. By n = 15, the ratio exceeds 2,600. The lattice you filled by hand is the structure that makes this compression possible: 2^n subsets instead of n! permutations, because the bitmask captures everything the DP needs.

Bitmask DP isn't a single trick — it's a pattern detector. Whenever a problem asks you to “assign items to slots” or “visit all nodes exactly once” or “partition a set optimally,” and the item count is small (typically n <= 20), check for the bitmask DP signal: the set of used items is all that matters, not the order.

The assignment problem you solved is one instance. The Traveling Salesman Problem is another — the “visited cities” bitmask replaces factorial path enumeration. Hamiltonian path, minimum-cost set cover, task scheduling with dependencies — all share the same skeletal structure: a lattice of subsets, bottom-up DP, and exponential-over-factorial compression.

The key recognition trigger: if the problem has n <= 20 items, requires exhaustive assignment or visitation, and the order doesn't affect future choices — reach for bitmask DP.

Match each problem below to the signal that unlocks the technique.