Number of Ways to Wear Different Hats to Each Other - Video Solutions

Problem Overview: Each person has a list of hats they are willing to wear. Every person must wear exactly one hat and no two people can wear the same hat. The task is to count how many valid assignments exist. The constraints are small for people (≤10) but large for hat IDs (≤40), which pushes you toward bitmask-based state compression.

Approach 1: Backtracking with Memoization (O(40 * 2^n) time, O(2^n) space)

Backtracking tries every valid assignment of hats to people. Instead of iterating people first, iterate hats from 1..40 and decide whether to assign the current hat to any eligible person who is still unassigned. Track assigned people using a bitmask where bit i indicates whether person i already has a hat. The recursion state becomes (hatIndex, mask). Memoization avoids recomputing the same state when the same combination of processed hats and assigned people appears again. This drastically reduces the search space because there are at most 40 * 2^n states.

The key insight is flipping the mapping: build a list of people for each hat rather than hats for each person. That lets you process hats sequentially and maintain the assignment mask efficiently using bitmask operations.

Approach 2: Dynamic Programming with Bitmasking (O(40 * 2^n) time, O(2^n) space)

The optimal solution models the problem as DP over subsets. Define dp[mask] as the number of ways to assign hats such that the set of people represented by mask already have hats. Iterate hats from 1..40, and for each hat update states where that hat is given to a compatible person. If person p likes the current hat and the bit for p is not set in mask, transition to mask | (1 << p). This builds assignments incrementally while guaranteeing that each hat is used at most once.

This works because the number of people is small. A mask of size n ≤ 10 produces at most 2^10 states, making the DP manageable. Each hat only transitions from existing masks, producing a total complexity of roughly 40 * 2^n. This technique is a classic combination of dynamic programming and bitmask state compression.

Recommended for interviews: The dynamic programming with bitmasking approach is the expected solution. Interviewers want to see that you recognize the small number of people and encode assignment states using a bitmask. Implementing the recursive backtracking version with memoization still demonstrates the same insight and is often easier to reason about during discussion. Showing both approaches signals strong understanding of subset DP and state compression techniques commonly used in array and combinatorial problems.