DP — Number of Ways to Wear Different Hats to Each Other
↗ LeetCode: Number of Ways to Wear Different Hats to Each Other · Hard · pattern chapter →
n people (≤ 10), 40 hats. Each person has preferences. Each hat used by ≤ 1 person; each person wears one. Count assignments (mod 1e9+7).
Example 1 — hats=[[3,4],[4,5],[5]] → 1 (one valid assignment) Example 2 — hats=[[3,5,1],[3,5]] → 4Example 3 — hats=[[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]] → 24 (4!)
Constraints — 1 ≤ n ≤ 10; hats ≤ 40. Brute over 40! hat orderings ≈ 8·10⁴⁷ ops — 10⁹ ops/sec = 10³¹ year (dies). Bitmask DP over people (n ≤ 10 → 2ⁿ=1024 states) iterating hats is O(40·2ⁿ·n) = 4·10⁵ ops = <1 min even under stress; ~10⁶ ops/sec throughput at production.
Interview timer00:00
Approach 1 — Brute assignment enumeration
Intuition. Try every hat→person assignment (or every person→hat with backtracking). Explodes with 40 hats and forbidden repeats.
Complexity — Time O(40ⁿ) even with pruning; Space O(n). TLE past n=7. In an interview say "n ≤ 10 → 2ⁿ ≤ 1024. Iterate over hats (large), keep 2ⁿ state over people (small)."
Approach 2 — Bitmask DP iterating hats (canonical)
Insight. dp[h][mask] = # ways to satisfy people in mask using hats 1..h. Transition: skip hat h, or give it to any person p in mask who likes it. Rolling 1D over mask.
int MOD = 1_000_000_007;
int numberWays(List<List<Integer>> hats) {
int n = hats.size(), full = 1 << n;
List<List<Integer>> hatToPeople = new ArrayList<>();
for (int i = 0; i <= 40; i++) hatToPeople.add(new ArrayList<>());
for (int p = 0; p < n; p++) for (int h : hats.get(p)) hatToPeople.get(h).add(p);
int[] dp = new int[full];
dp[0] = 1;
for (int h = 1; h <= 40; h++) {
int[] nd = dp.clone();
for (int mask = 0; mask < full; mask++)
for (int p : hatToPeople.get(h))
if ((mask & (1 << p)) == 0)
nd[mask | (1 << p)] = (nd[mask | (1 << p)] + dp[mask]) % MOD;
dp = nd;
}
return dp[full - 1];
}Complexity — Time O(40 · 2ⁿ · n); Space O(2ⁿ). Say aloud in an interview: "always mask the smaller side — same trick as assignment problems, Beautiful Arrangement, k-partitions."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute enum | O(40ⁿ) | O(n) | TLE past n=7 |
| Bitmask over people | O(40·2ⁿ·n) | O(2ⁿ) | Canonical |
When to use which
- Small n (≤ 10), large "items" domain → iterate items, mask people.
- Small items, large people → reverse.