There are n people and 40 types of hats labeled from 1 to 40.
Given a 2D integer array hats, where hats[i] is a list of all hats preferred by the ith person.
Return the number of ways that the n people wear different hats to each other.
Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: hats = [[3,4],[4,5],[5]] Output: 1 Explanation: There is only one way to choose hats given the conditions. First person choose hat 3, Second person choose hat 4 and last one hat 5.
Example 2:
Input: hats = [[3,5,1],[3,5]] Output: 4 Explanation: There are 4 ways to choose hats: (3,5), (5,3), (1,3) and (1,5)
Example 3:
Input: hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]] Output: 24 Explanation: Each person can choose hats labeled from 1 to 4. Number of Permutations of (1,2,3,4) = 24.
Constraints:
n == hats.length1 <= n <= 101 <= hats[i].length <= 401 <= hats[i][j] <= 40hats[i] contains a list of unique integers.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.
This approach involves using backtracking to try all possible assignments of hats by recursively assigning hats to people.
We use memoization to store already computed results to avoid redundant calculations, improving efficiency.
We implemented a `ways` function that checks each hat number iteratively and recursively assigns it to available people.
Using a bit mask helps track which people have already been assigned hats.
Memoization is employed to cache results of previously computed states.
Python
JavaScript
Time Complexity: O(2^n * 40) where `n` is the number of people.
Space Complexity: O(2^n * 40) due to memoization storage.
We use dynamic programming and bitmasking to efficiently calculate the number of distinct hat placements.
Each state is represented by a bitmask indicating which people have been assigned hats.
Transition between states occurs by considering each hat for each person who prefers it.
This C++ solution executes a depth-first search with memoization, similar to backtracking but driven by dynamic programming principles.
It uses bitmasking to determine available states efficiently, and transitions between states by considering hat availability for each person.
Time Complexity: O(2^n * 40)
Space Complexity: O(2^n * 40)
We notice that n is not greater than 10, so we consider using DP with state compression to solve this problem.
We define f[i][j] as the number of ways to assign the first i hats to the people whose state is j. Here j is a binary number, which represents a set of people. We have f[0][0]=1 at the beginning, and the answer is f[m][2^n - 1], where m is the maximum number of hats and n is the number of people.
Consider f[i][j]. If we don't assign the i-th hat to anyone, then f[i][j]=f[i-1][j]; if we assign the i-th hat to the person k who likes it, then f[i][j]=f[i-1][j \oplus 2^k]. Here \oplus denotes the XOR operation. Therefore, we can get the state transition equation:
$
f[i][j]=f[i-1][j]+ sum_{k \in like[i]} f[i-1][j \oplus 2^k]
where like[i] denotes the set of people who like the i-th hat.
The final answer is f[m][2^n - 1], and the answer may be very large, so we need to take it modulo 10^9 + 7.
Time complexity O(m times 2^n times n), space complexity O(m times 2^n). Here m is the maximum number of hats, which is no more than 40 in this problem; and n is the number of people, which is no more than 10$ in this problem.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Backtracking with Memoization | Time Complexity: O(2^n * 40) where `n` is the number of people. Space Complexity: O(2^n * 40) due to memoization storage. |
| Dynamic Programming with Bitmasking | Time Complexity: O(2^n * 40) Space Complexity: O(2^n * 40) |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Memoization | O(40 * 2^n) | O(2^n) | Good for understanding the assignment search space and building intuition for subset states |
| Dynamic Programming with Bitmasking | O(40 * 2^n) | O(2^n) | Best approach when the number of people is small and each state can be represented using a bitmask |
Number of Ways to Wear Different Hats to Each Other: 1434 • Tony Teaches • 2,173 views views
Watch 6 more video solutions →Practice Number of Ways to Wear Different Hats to Each Other with our built-in code editor and test cases.
Practice on FleetCode