853. Hats for Everyone
A costume party has n guests and exactly 40 kinds of hats, numbered 1 to 40, with one hat of each kind. Guest i is willing to wear any hat listed in hats[i] (the list has no repeated kinds).
Every guest must wear exactly one hat from their own list, and no two guests may wear the same kind of hat. Count the number of different ways to hand out the hats, where two ways differ if some guest wears a different kind. Because the count can be huge, return it modulo 10^9 + 7. If no valid hand-out exists, return 0.
Example 1
- Input:
- hats = [[1,2],[2,3]]
- Output:
- 3
- Explanation:
Valid pairs of hats are (1,2), (1,3) and (2,3) for the two people; (2,2) is forbidden because the hat is shared, so 3 ways.
Example 2
- Input:
- hats = [[5],[5,9],[9,12]]
- Output:
- 1
- Explanation:
The first person must wear 5, forcing the second to take 9 and the third 12, giving exactly 1 way.
Constraints
- 1 ≤ n ≤ 10
- 1 ≤ hats[i].length ≤ 40
- 1 ≤ hats[i][j] ≤ 40, all values in one list are distinct
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(40 * 2^n * n)
- Space
- O(2^n)