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

1
2
3
4

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

1
2
3
4

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

1
2
3
4

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.

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

  1. Build a mapping from each hat to the list of people who like it.
  2. Use a DP array where dp[mask] is the number of ways to assign hats to the subset of people represented by mask.
  3. 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.
  4. The answer is dp[full_mask] where all people have hats.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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]
 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

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]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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.