Show problems as
Classic problem #1434HardArrayDynamic ProgrammingBit ManipulationBitmaskBipartite GraphMatching (Graph)Perfect Matching

Number of Ways to Wear Different Hats to Each Other

Real-world version: Handing Out Badges Nobody Shares
Tracked in this browser only
Read Number of Ways to Wear Different Hats to Each Other on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

There are some staff, and hats[i] lists the badge numbers that would suit staff member i. Every list holds distinct numbers.

Every staff member is given exactly one badge that suits them, and no two are given the same badge.

Return how many ways that can be done, modulo 10^9 + 7.

Examples

Example 1

Input
hats = [[1, 2], [1, 2]]
Output
2

Both staff would take either badge, so one takes 1 and the other 2, or the other way round.

Example 2

Input
hats = [[1], [1]]
Output
0

Both staff would only take badge 1, and it cannot be shared.

Example 3

Input
hats = [[1, 2, 3, 4], [2, 3], [3]]
Output
2

Badge 3 must go to the third staff member, so badge 2 must go to the second, and the first is left with badge 1 or 4.

Constraints

  • 1 <= hats.length <= 10
  • 1 <= hats[i].length <= 40
  • 1 <= hats[i][j] <= 40
  • The numbers in hats[i] are all different

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def number_ways(hats: list[list[int]]) -> int:
Java
public int numberWays(List<List<Integer>> hats)

More on the same topics