Number of Ways to Wear Different Hats to Each Other
HardUpdated: Aug 2, 2025
Practice on:
Problem
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 n people can wear different hats from each other.
Since the answer may be too large, return it modulo 10^9 + 7.
Examples
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.
Solution
Method 1 – Bitmask Dynamic Programming
Intuition
We use bitmask DP to represent which people have already been assigned hats. For each hat, we try to assign it to any person who likes it and hasn't been assigned a hat yet. We iterate over all hats and update the DP accordingly.
Approach
- Build a mapping from each hat to the list of people who like it.
- Use a DP array where
dp[mask]is the number of ways to assign hats to the subset of people represented bymask. - Iterate over hats 1 to 40:
- For each mask, for each person who likes the current hat and hasn't been assigned a hat (mask bit is 0), update the DP for the new mask.
- The answer is
dp[full_mask]where all people have hats.
Code
C++
class Solution {
public:
int numberWays(vector<vector<int>>& hats) {
int n = hats.size(), mod = 1e9+7;
vector<vector<int>> hat2people(41);
for (int i = 0; i < n; ++i)
for (int h : hats[i]) hat2people[h].push_back(i);
vector<int> dp(1<<n);
dp[0] = 1;
for (int h = 1; h <= 40; ++h) {
vector<int> ndp = dp;
for (int mask = 0; mask < (1<<n); ++mask) {
for (int p : hat2people[h]) {
if (!(mask & (1<<p))) {
ndp[mask | (1<<p)] = (ndp[mask | (1<<p)] + dp[mask]) % mod;
}
}
}
dp = ndp;
}
return dp[(1<<n)-1];
}
};
Go
func numberWays(hats [][]int) int {
n, mod := len(hats), int(1e9+7)
hat2people := make([][]int, 41)
for i := 0; i < n; i++ {
for _, h := range hats[i] {
hat2people[h] = append(hat2people[h], i)
}
}
dp := make([]int, 1<<n)
dp[0] = 1
for h := 1; h <= 40; h++ {
ndp := make([]int, 1<<n)
copy(ndp, dp)
for mask := 0; mask < (1<<n); mask++ {
for _, p := range hat2people[h] {
if mask&(1<<p) == 0 {
ndp[mask|(1<<p)] = (ndp[mask|(1<<p)] + dp[mask]) % mod
}
}
}
dp = ndp
}
return dp[(1<<n)-1]
}
Java
class Solution {
public int numberWays(List<List<Integer>> hats) {
int n = hats.size(), mod = 1000000007;
List<Integer>[] hat2people = new List[41];
for (int i = 0; i < 41; ++i) hat2people[i] = new ArrayList<>();
for (int i = 0; i < n; ++i)
for (int h : hats.get(i)) hat2people[h].add(i);
int[] dp = new int[1<<n];
dp[0] = 1;
for (int h = 1; h <= 40; ++h) {
int[] ndp = dp.clone();
for (int mask = 0; mask < (1<<n); ++mask) {
for (int p : hat2people[h]) {
if ((mask & (1<<p)) == 0) {
ndp[mask | (1<<p)] = (ndp[mask | (1<<p)] + dp[mask]) % mod;
}
}
}
dp = ndp;
}
return dp[(1<<n)-1];
}
}
Kotlin
class Solution {
fun numberWays(hats: List<List<Int>>): Int {
val n = hats.size
val mod = 1_000_000_007
val hat2people = Array(41) { mutableListOf<Int>() }
for (i in 0 until n)
for (h in hats[i]) hat2people[h].add(i)
var dp = IntArray(1 shl n)
dp[0] = 1
for (h in 1..40) {
val ndp = dp.copyOf()
for (mask in 0 until (1 shl n)) {
for (p in hat2people[h]) {
if (mask and (1 shl p) == 0) {
ndp[mask or (1 shl p)] = (ndp[mask or (1 shl p)] + dp[mask]) % mod
}
}
}
dp = ndp
}
return dp[(1 shl n) - 1]
}
}
Python
class Solution:
def numberWays(self, hats: list[list[int]]) -> int:
n, mod = len(hats), 10**9+7
hat2people = [[] for _ in range(41)]
for i, hs in enumerate(hats):
for h in hs:
hat2people[h].append(i)
dp = [0] * (1<<n)
dp[0] = 1
for h in range(1, 41):
ndp = dp[:]
for mask in range(1<<n):
for p in hat2people[h]:
if not (mask & (1<<p)):
ndp[mask | (1<<p)] = (ndp[mask | (1<<p)] + dp[mask]) % mod
dp = ndp
return dp[(1<<n)-1]
Rust
impl Solution {
pub fn number_ways(hats: Vec<Vec<i32>>) -> i32 {
let n = hats.len();
let modv = 1_000_000_007;
let mut hat2people = vec![vec![]; 41];
for (i, hs) in hats.iter().enumerate() {
for &h in hs {
hat2people[h as usize].push(i);
}
}
let mut dp = vec![0; 1<<n];
dp[0] = 1;
for h in 1..=40 {
let mut ndp = dp.clone();
for mask in 0..(1<<n) {
for &p in &hat2people[h] {
if mask & (1<<p) == 0 {
ndp[mask | (1<<p)] = (ndp[mask | (1<<p)] + dp[mask]) % modv;
}
}
}
dp = ndp;
}
dp[(1<<n)-1]
}
}
TypeScript
class Solution {
numberWays(hats: number[][]): number {
const n = hats.length, mod = 1e9+7;
const hat2people: number[][] = Array.from({length: 41}, () => []);
for (let i = 0; i < n; ++i)
for (const h of hats[i]) hat2people[h].push(i);
let dp = Array(1<<n).fill(0);
dp[0] = 1;
for (let h = 1; h <= 40; ++h) {
const ndp = dp.slice();
for (let mask = 0; mask < (1<<n); ++mask) {
for (const p of hat2people[h]) {
if ((mask & (1<<p)) === 0) {
ndp[mask | (1<<p)] = (ndp[mask | (1<<p)] + dp[mask]) % mod;
}
}
}
dp = ndp;
}
return dp[(1<<n)-1];
}
}
Complexity
- ⏰ Time complexity:
O(40 * n * 2^n)— For each hat, we process all masks and people. - 🧺 Space complexity:
O(2^n)— For the DP array.