Hard

Number of Ways to Wear Different Hats to Each Other

LAB

Given each person's acceptable hats, return the number of assignments where every person gets a different acceptable hat.

EXAMPLES

Example 1

Input
{
  "hats": [
    [
      3,
      4
    ],
    [
      4,
      5
    ],
    [
      5
    ]
  ]
}

Output
1

FUNCTION SHAPE

hats: intMatrix→int

SOLUTION NOTE

Iterate over hats (40), mask tracks assigned people (n ≤ 10). Invert the problem for smaller state space.

Reveal reference solution +

pythonREFERENCE

def numberWays(self, hats: List[List[int]]) -> int:
    MOD = 10 ** 9 + 7
    n = len(hats)

    # Invert: for each hat, which people can wear it
    hat_to_people = defaultdict(list)
    for person, hat_list in enumerate(hats):
        for hat in hat_list:
            hat_to_people[hat].append(person)

    @cache
    def dp(hat, mask):
        if mask == (1 << n) - 1:
            return 1
        if hat > 40:
            return 0

        # Don't use this hat
        res = dp(hat + 1, mask)

        # Assign this hat to someone who wants it and isn't assigned
        for person in hat_to_people[hat]:
            if not (mask & (1 << person)):
                res = (res + dp(hat + 1, mask | (1 << person))) % MOD

        return res

    return dp(1, 0)

TimeO(40 × n × 2^n)

SpaceO(40 × 2^n)

Open on LeetCode ↗