LeetCode 1434. Number of Ways to Wear Different Hats to Each Other Solution in Java, C++, Python & More | Explanation + Code

Description

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 109 + 7.

 

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 chooses hat 3, Second person chooses 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.length
• 1 <= n <= 10
• 1 <= hats[i].length <= 40
• 1 <= hats[i][j] <= 40
• hats[i] contains a list of unique integers.

Solutions

Solution 1: Dynamic Programming

We notice that n is not greater than 10, so we consider using DP with state compression to solve this problem.

We define f[i][j] as the number of ways to assign the first i hats to the people whose state is j. Here j is a binary number, which represents a set of people. We have f[0][0]=1 at the beginning, and the answer is f[m][2ⁿ - 1], where m is the maximum number of hats and n is the number of people.

Consider f[i][j]. If we don't assign the i-th hat to anyone, then f[i][j]=f[i-1][j]; if we assign the i-th hat to the person k who likes it, then f[i][j]=f[i-1][j \oplus 2^k]. Here \oplus denotes the XOR operation. Therefore, we can get the state transition equation:

f[i][j]=f[i-1][j]+ ∑_{k ∈ like[i]} f[i-1][j \oplus 2^k]

where like[i] denotes the set of people who like the i-th hat.

The final answer is f[m][2ⁿ - 1], and the answer may be very large, so we need to take it modulo 10⁹ + 7.

Time complexity O(m × 2ⁿ × n), space complexity O(m × 2ⁿ). Here m is the maximum number of hats, which is no more than 40 in this problem; and n is the number of people, which is no more than 10 in this problem.

PythonJavaC++GoTypeScript

class Solution: def numberWays(self, hats: List[List[int]]) -> int: g = defaultdict(list) for i, h in enumerate(hats): for v in h: g[v].append(i) mod = 10**9 + 7 n = len(hats) m = max(max(h) for h in hats) f = [[0] * (1 << n) for _ in range(m + 1)] f[0][0] = 1 for i in range(1, m + 1): for j in range(1 << n): f[i][j] = f[i - 1][j] for k in g[i]: if j >> k & 1: f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod return f[m][-1](code-box)

class Solution { public int numberWays(List<List<Integer>> hats) { int n = hats.size(); int m = 0; for (var h : hats) { for (int v : h) { m = Math.max(m, v); } } List<Integer>[] g = new List[m + 1]; Arrays.setAll(g, k -> new ArrayList<>()); for (int i = 0; i < n; ++i) { for (int v : hats.get(i)) { g[v].add(i); } } final int mod = (int) 1e9 + 7; int[][] f = new int[m + 1][1 << n]; f[0][0] = 1; for (int i = 1; i <= m; ++i) { for (int j = 0; j < 1 << n; ++j) { f[i][j] = f[i - 1][j]; for (int k : g[i]) { if ((j >> k & 1) == 1) { f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod; } } } } return f[m][(1 << n) - 1]; } }(code-box)

class Solution { public: int numberWays(vector<vector<int>>& hats) { int n = hats.size(); int m = 0; for (auto& h : hats) { m = max(m, *max_element(h.begin(), h.end())); } vector<vector<int>> g(m + 1); for (int i = 0; i < n; ++i) { for (int& v : hats[i]) { g[v].push_back(i); } } const int mod = 1e9 + 7; int f[m + 1][1 << n]; memset(f, 0, sizeof(f)); f[0][0] = 1; for (int i = 1; i <= m; ++i) { for (int j = 0; j < 1 << n; ++j) { f[i][j] = f[i - 1][j]; for (int k : g[i]) { if (j >> k & 1) { f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod; } } } } return f[m][(1 << n) - 1]; } };(code-box)

func numberWays(hats [][]int) int { n := len(hats) m := 0 for _, h := range hats { m = max(m, slices.Max(h)) } g := make([][]int, m+1) for i, h := range hats { for _, v := range h { g[v] = append(g[v], i) } } const mod = 1e9 + 7 f := make([][]int, m+1) for i := range f { f[i] = make([]int, 1<<n) } f[0][0] = 1 for i := 1; i <= m; i++ { for j := 0; j < 1<<n; j++ { f[i][j] = f[i-1][j] for _, k := range g[i] { if j>>k&1 == 1 { f[i][j] = (f[i][j] + f[i-1][j^(1<<k)]) % mod } } } } return f[m][(1<<n)-1] }(code-box)

function numberWays(hats: number[][]): number { const n = hats.length; const m = Math.max(...hats.flat()); const g: number[][] = Array.from({ length: m + 1 }, () => []); for (let i = 0; i < n; ++i) { for (const v of hats[i]) { g[v].push(i); } } const f: number[][] = Array.from({ length: m + 1 }, () => Array.from({ length: 1 << n }, () => 0), ); f[0][0] = 1; const mod = 1e9 + 7; for (let i = 1; i <= m; ++i) { for (let j = 0; j < 1 << n; ++j) { f[i][j] = f[i - 1][j]; for (const k of g[i]) { if (((j >> k) & 1) === 1) { f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod; } } } } return f[m][(1 << n) - 1]; }(code-box)