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.

c++

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);
    }
};