Sponsored
Sponsored
This approach involves using backtracking to try all possible assignments of hats by recursively assigning hats to people.
We use memoization to store already computed results to avoid redundant calculations, improving efficiency.
Time Complexity: O(2^n * 40) where `n` is the number of people.
Space Complexity: O(2^n * 40) due to memoization storage.
1const MOD = 10**9 + 7;
2
3function numberOfWays(hats) {
4 const n = hats.length;
5 const allMask = (1 << n) - 1;
6 const dp = new Map();
7 const hatToPeople = Array.from({ length: 41 }, () => []);
8
9 hats.forEach((hatList, person) => {
10 hatList.forEach(hat => {
11 hatToPeople[hat].push(person);
12 });
13 });
14
15 function ways(hat, mask) {
16 if (mask === allMask) return 1;
17 if (hat > 40) return 0;
18 const key = `${hat},${mask}`;
19 if (dp.has(key)) return dp.get(key);
20 let ans = ways(hat + 1, mask);
21 hatToPeople[hat].forEach(person => {
22 if ((mask & (1 << person)) === 0) {
23 ans += ways(hat + 1, mask | (1 << person));
24 ans %= MOD;
25 }
26 });
27 dp.set(key, ans);
28 return ans;
29 }
30
31 return ways(1, 0);
32}Similar to the Python solution, we use a recursive function supported by memoization and bit masking to determine valid hat distributions.
We use dynamic programming and bitmasking to efficiently calculate the number of distinct hat placements.
Each state is represented by a bitmask indicating which people have been assigned hats.
Transition between states occurs by considering each hat for each person who prefers it.
Time Complexity: O(2^n * 40)
Space Complexity: O(2^n * 40)
1import java.util.*;
2
3
This Java solution uses bitmasking and memoization, implementing a depth-first search while protecting against over-counting by storing results in a map.