[LeetCode] Number of Ways to Wear Different Hats to Each Other

1434. Number of Ways to Wear Different Hats to Each Other

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
long dp[41][1<<10];
int mod = 1e9 + 7;
int allSelected = 0;
int maHat = 0;
long helper(int mask, unordered_map<int, vector<int>>& peoples, int hat) {
if(mask == allSelected) return 1l;
if(hat == maHat) return 0l;
if(dp[hat][mask] != -1) return dp[hat][mask];
long& res = dp[hat][mask] = helper(mask, peoples, hat + 1);

for(auto p : peoples[hat]) {
if(mask & 1<<p) continue;
res = (res + helper(mask | 1<<p, peoples, hat + 1)) % mod;
}

return res;
}
public:
int numberWays(vector<vector<int>>& hats) {
memset(dp,-1,sizeof(dp));
unordered_map<int,vector<int>> peoples;
int n = hats.size();
allSelected = (1<<n) - 1;
for(int i = 0; i < n; i++) {
for(auto h : hats[i]) {
peoples[h].push_back(i);
maHat = max(maHat, h);
}
}
maHat += 1;

return helper(0,peoples,1);
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/03/11/PS/LeetCode/number-of-ways-to-wear-different-hats-to-each-other/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.