Advanced Conceptsbitmasksubset

Bitmasking and DP

Given n people, each willing to wear only certain caps drawn from a shared pool of cap types, count the number of ways to give every person a different cap, using only caps that person is willing to wear.

Do this lesson first: coin change

Example input

likes = [[1, 2, 5], [1, 3, 4], [2, 3, 6]] (person 0 wears caps 1, 2 or 5, and so on), cap types 1 to 4

Expected output

5

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[c][mask] is the number of ways to deal out cap types 1 to c, each to at most one person who likes it, so that exactly the people in mask end up wearing a cap, one cap each. The mask is a group of PEOPLE written in binary, bit p for person p. That choice is the insight the whole page is built around: the set that goes into the mask is the SMALL one. In the usual telling of this problem there are at most 10 people and 100 cap types. A mask over people has 2^10 = 1024 values; a mask over cap types would have 2^100, a number with 31 digits. So the people become the mask and the cap types become an ordinary loop. A loop is all the caps need: they are dealt in order, and once the loop moves past cap c it is never offered again, so nothing has to remember which caps are used. People are not served in any order, since any of them may end up with any cap, so the table has to remember who is already covered. That memory is the mask.

dp[c][mask] = dp[c - 1][mask] + sum over persons p in mask who like cap c of dp[c - 1][mask without p]

Ask what happened to cap type c, the last one dealt with. Either nobody wore it, and then the people in mask got their caps from types 1 to c - 1: dp[c - 1][mask] ways. Or exactly one person p in mask wore it, which needs p to like cap c, and then everyone else in mask got their caps from types 1 to c - 1: dp[c - 1][mask without p] ways. No assignment falls under two of these options, because cap c's fate is different in each, and none falls under no option, so the counts ADD. Distinctness takes care of itself: each cap type is handed to one person at most, and each person leaves the mask the moment they are covered. In code, mask without p is mask & ~(1 << p).

Row 0 is given: with no cap types dealt out yet, the only possible group is nobody, so dp[0][000] = 1, the empty assignment, and every other dp[0][mask] = 0. Every later cell reads only the row directly above it, so filling top to bottom is enough, and within a row the order does not matter. The answer is the bottom-right cell, every cap type considered and every person covered. Cells for partial groups are not wasted: dp[3][101], persons 0 and 2 covered by caps 1 to 3, is exactly what row 4 reads when cap 4 goes to person 1.

Tabulation with C computed rows of 2^n cells below the given row 0, each summing at most n + 1 cells from the row above. Because a cell only reads the row above, and only at its own mask or a smaller one, a single array of 2^n numbers is enough if each row sweeps the masks from the top down: the smaller masks a cell needs have not been overwritten yet, the same trick that shrinks 0/1 knapsack to one row. With 10 people and 100 cap types that is 1024 numbers and about a million inner-loop steps.

Time O(C × 2^n × n), for C cap types and n people, with each like looked up in constant timeSpace O(C × 2^n), reducible to O(2^n)

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Row 0 is given: with no cap types dealt out yet, the only possible group is nobody, so dp[0][000] = 1, the empty assignment, and every other dp[0][mask] = 0. Every later cell reads only the row directly above it, so filling top to bottom is enough, and within a row the order does not matter. The answer is the bottom-right cell, every cap type considered and every person covered. Cells for partial groups are not wasted: dp[3][101], persons 0 and 2 covered by caps 1 to 3, is exactly what row 4 reads when cap 4 goes to person 1.

Rows ↓
Cols →

000

001

010

011

100

101

110

111

0

1

0

1

0

2

1

2

1

0

3

1

2

3

2

3

2

4

1

2

3

5

2

3

5

Rows ↓c: cap types 1 to c have been dealt with

Cols →mask: who is already wearing a cap, bit p for person p

bitmasking-and-dp.ts

1function capWays(likes, caps) {
2 const n = likes.length, FULL = (1 << n) - 1;
3 const dp = [];
4 dp[0] = Array.from({ length: FULL + 1 }, (_, m) => (m === 0 ? 1 : 0));
5 for (let c = 1; c <= caps; c++) {
6 dp[c] = [];
7 for (let mask = 0; mask <= FULL; mask++) {
8 let ways = dp[c - 1][mask]; // cap c stays on the shelf
9 for (let p = 0; p < n; p++)
10 if (mask & (1 << p) && likes[p].includes(c))
11 ways += dp[c - 1][mask & ~(1 << p)]; // cap c goes to person p
12 dp[c][mask] = ways;
13 }
14 }
15 return dp[caps][FULL];
16}

Base caseComputedBeing readAnswer

The code, the trap, the variations

bitmasking-and-dp.ts

1function capWays(likes, caps) {
2 const n = likes.length, FULL = (1 << n) - 1;
3 const dp = [];
4 dp[0] = Array.from({ length: FULL + 1 }, (_, m) => (m === 0 ? 1 : 0));
5 for (let c = 1; c <= caps; c++) {
6 dp[c] = [];
7 for (let mask = 0; mask <= FULL; mask++) {
8 let ways = dp[c - 1][mask]; // cap c stays on the shelf
9 for (let p = 0; p < n; p++)
10 if (mask & (1 << p) && likes[p].includes(c))
11 ways += dp[c - 1][mask & ~(1 << p)]; // cap c goes to person p
12 dp[c][mask] = ways;
13 }
14 }
15 return dp[caps][FULL];
16}

Where people go wrong

Putting the caps in the mask. It is a common first attempt, because the caps are what gets used up, and it works on toy inputs, but a mask over 100 cap types has 2^100 values and no table will ever hold it. The rule to carry away: the mask goes on whichever set is small, and here that is the people. The other common slip is skipping the table and multiplying each person's options. With caps 1 to 4 that is 2 × 3 × 2 = 12, against the true 5, because the product happily gives cap 1 to persons 0 and 1 at once.

Drop the rule that caps must differ, so two people may wear the same type.
The mask stops being needed at all. With no clash to avoid, people choose independently and the answer is the product of how many caps each one likes, 12 for caps 1 to 4. The question and the inputs are unchanged; what disappears is the reason for the mask, which only existed because each cap type goes to one person at most, and that forces the table to remember who is covered.
Each cap type comes in k copies, so up to k people can wear the same type.
The state is unchanged. The transition widens: instead of giving cap c to one person in mask, give it to any group of at most k people in mask who all like it, and add dp[c - 1][mask without that group] for each such group. The row-by-row order is unchanged.
Add a fourth person.
The table doubles in width to 16 masks, past this page's 12-column budget, which is why it stops at three people. The method itself is unchanged. The cost grows exponentially with the people and only linearly with the caps: every extra person doubles the row, so 20 people means rows of 2^20, about a million cells, while every extra cap type adds one more row.

Traveling Salesman Problem