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 by mask.
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

[{"language":"C++","code":"class Solution {\npublic:\n    int numberWays(vector<vector<int>>& hats) {\n        int n = hats.size(), mod = 1e9+7;\n        vector<vector<int>> hat2people(41);\n        for (int i = 0; i < n; ++i)\n            for (int h : hats[i]) hat2people[h].push_back(i);\n        vector<int> dp(1<<n);\n        dp[0] = 1;\n        for (int h = 1; h <= 40; ++h) {\n            vector<int> ndp = dp;\n            for (int mask = 0; mask < (1<<n); ++mask) {\n                for (int p : hat2people[h]) {\n                    if (!(mask & (1<<p))) {\n                        ndp[mask | (1<<p)] = (ndp[mask | (1<<p)] + dp[mask]) % mod;\n                    }\n                }\n            }\n            dp = ndp;\n        }\n        return dp[(1<<n)-1];\n    }\n};","lang":"cpp"},{"language":"Go","code":"func numberWays(hats [][]int) int {\n    n, mod := len(hats), int(1e9+7)\n    hat2people := make([][]int, 41)\n    for i := 0; i < n; i++ {\n        for _, h := range hats[i] {\n            hat2people[h] = append(hat2people[h], i)\n        }\n    }\n    dp := make([]int, 1<<n)\n    dp[0] = 1\n    for h := 1; h <= 40; h++ {\n        ndp := make([]int, 1<<n)\n        copy(ndp, dp)\n        for mask := 0; mask < (1<<n); mask++ {\n            for _, p := range hat2people[h] {\n                if mask&(1<<p) == 0 {\n                    ndp[mask|(1<<p)] = (ndp[mask|(1<<p)] + dp[mask]) % mod\n                }\n            }\n        }\n        dp = ndp\n    }\n    return dp[(1<<n)-1]\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public int numberWays(List<List<Integer>> hats) {\n        int n = hats.size(), mod = 1000000007;\n        List<Integer>[] hat2people = new List[41];\n        for (int i = 0; i < 41; ++i) hat2people[i] = new ArrayList<>();\n        for (int i = 0; i < n; ++i)\n            for (int h : hats.get(i)) hat2people[h].add(i);\n        int[] dp = new int[1<<n];\n        dp[0] = 1;\n        for (int h = 1; h <= 40; ++h) {\n            int[] ndp = dp.clone();\n            for (int mask = 0; mask < (1<<n); ++mask) {\n                for (int p : hat2people[h]) {\n                    if ((mask & (1<<p)) == 0) {\n                        ndp[mask | (1<<p)] = (ndp[mask | (1<<p)] + dp[mask]) % mod;\n                    }\n                }\n            }\n            dp = ndp;\n        }\n        return dp[(1<<n)-1];\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun numberWays(hats: List<List<Int>>): Int {\n        val n = hats.size\n        val mod = 1_000_000_007\n        val hat2people = Array(41) { mutableListOf<Int>() }\n        for (i in 0 until n)\n

Related Tags