Skip to main content
Talentd

Number of Ways to Wear Different Hats to Each Other - Solution & Explanation

HardArrayDynamic ProgrammingBit ManipulationBitmask14 min readAsked at: Roblox, De Shaw, Mindtickle
Practice this problem

Problem Statement

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.length
  • 1 <= n <= 10
  • 1 <= hats[i].length <= 40
  • 1 <= hats[i][j] <= 40
  • hats[i] contains a list of unique integers.

Approach Overview

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.

Approach 1: Backtracking with Memoization

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(2^n * 40) where `n` is the number of people.

Space Complexity: O(2^n * 40) due to memoization storage.

Try this approach in the editor →

Approach 2: Dynamic Programming with Bitmasking

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.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(2^n * 40)

Space Complexity: O(2^n * 40)

Try this approach in the editor →

Approach 3: Dynamic Programming

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with MemoizationO(40 * 2^n)O(2^n)Good for understanding the assignment search space and building intuition for subset states
Dynamic Programming with BitmaskingO(40 * 2^n)O(2^n)Best approach when the number of people is small and each state can be represented using a bitmask

Video Solution

Number of Ways to Wear Different Hats to Each Other: 1434 • Tony Teaches • 2,297 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Number of Ways to Wear Different Hats to Each Other easy or hard?
The problem is classified as Hard on LeetCode. The difficulty comes from recognizing the need for subset DP and using bitmask state compression to represent assignments efficiently.
Number of Ways to Wear Different Hats to Each Other Python/Java solution
Python solutions commonly implement recursion with memoization using a bitmask to track assigned people. Java and C++ solutions often use iterative DP arrays indexed by mask. Both implementations rely on the same O(40 * 2^n) state transitions.
How to solve Number of Ways to Wear Different Hats to Each Other in O(n)?
An O(n) solution is not possible because the problem requires exploring combinations of assignments. The best known approach runs in O(40 * 2^n) using bitmask dynamic programming. Since the number of people is at most 10, the subset space (2^n) remains small enough to compute efficiently.
What is the best approach for Number of Ways to Wear Different Hats to Each Other?
Dynamic programming with bitmasking is the most efficient approach. Represent the set of people who already received hats using a bitmask and iterate through hats from 1 to 40. For each hat, update DP states by assigning it to compatible people. This yields O(40 * 2^n) time and O(2^n) space, which works because n ≤ 10.
Is Number of Ways to Wear Different Hats to Each Other asked at Google/Amazon/Meta?
Subset dynamic programming and bitmask assignment problems frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact question may vary, the underlying technique—DP over subsets with bitmasks—is a common interview pattern.
What data structure is used in Number of Ways to Wear Different Hats to Each Other?
The main data structure is a bitmask representing which people already have hats. Along with the bitmask, a dynamic programming array or memoization map stores the number of valid assignments for each state. A reversed mapping from hat to people who like it is also used for efficient iteration.
What is the time complexity of Number of Ways to Wear Different Hats to Each Other?
The optimal complexity is O(40 * 2^n), where n is the number of people. There are at most 40 hats and 2^n possible assignment states represented by a bitmask. Each hat processes transitions across these states, keeping the runtime manageable.

Ready to solve this problem?

Practice Number of Ways to Wear Different Hats to Each Other with our built-in code editor and test cases.

Practice on FleetCode
Previous

The Number of Good Subsets