#1434

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Ways to Wear Different Hats to Each Other

Calculate all unique assignments of hats to people using state transition dynamic programming with bitmasking for collisions.

array dynamic programming bit manipulation bitmask

Problem Statement

You are given n people and 40 different types of hats labeled from 1 to 40. Each person has a list of hats they prefer, represented by a 2D integer array hats where hats[i] contains the hat numbers preferred by the ith person.

Return the total number of ways to assign hats to people such that each person wears exactly one hat, no two people wear the same hat, and all assigned hats respect the individual preferences. For example, hats = [[3,4],[4,5],[5]] has only one valid assignment where each person gets a distinct preferred hat.

Examples

Example 1

Input: hats = [[3,4],[4,5],[5]]

Output: 1

There is only one way to choose hats given the conditions. First person choose hat 3, Second person choose hat 4 and last one hat 5.

Example 2

Input: hats = [[3,5,1],[3,5]]

Output: 4

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

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.

Solution Approach

Map Hats to People

First, invert the preference list to know for each hat which people can wear it. This simplifies state transitions since we can iterate over hats and update people assignments efficiently.

State Transition Dynamic Programming with Bitmask

Use a DP array where the index is a bitmask representing which people have been assigned hats. For each hat, iterate through all subsets of people who can wear it and update the DP states accordingly, ensuring no two people share the same hat.

Aggregate Valid Assignments

After processing all hats, the DP entry corresponding to all people assigned (bitmask of all 1s) gives the total number of valid assignments. Return this count modulo a large prime if required.

Complexity Analysis

Metric	Value
Time	O(k \cdot n \cdot 2^n)
Space	O(k \cdot 2^n)

Time complexity is O(k * n * 2^n) where k is the number of hats and n is the number of people, as each hat can update all DP states. Space complexity is O(k * 2^n) to store DP states for each hat.

What Interviewers Usually Probe

Focus on bitmask representation of people assignments.
Expect efficient state transition DP instead of brute-force permutation generation.
Watch for edge cases where a person prefers no hats or multiple hats overlap.

Common Pitfalls or Variants

Common pitfalls

Incorrectly updating DP states leading to double counting.
Failing to handle hats that no one prefers, causing state inconsistencies.
Ignoring modulus constraints which can cause integer overflow in large counts.

Follow-up variants

Restrict hats to a smaller fixed set and test DP scalability.
Allow multiple people to share the same hat and analyze state changes.
Compute the minimum number of hats needed for a valid assignment instead of counting all ways.

FAQ

What is the primary pattern in Number of Ways to Wear Different Hats to Each Other?

The primary pattern is state transition dynamic programming using bitmasking to represent people assigned hats.

How do I efficiently implement bitmask DP for this hats problem?

Represent assigned people as bits in an integer. Iterate over hats, updating DP states by setting bits for each possible person assignment without conflicts.

Can this approach handle all n <= 10 people?

Yes, with bitmask DP the 2^n states are feasible for n up to 10, ensuring quick updates for each hat.

Why not use permutations to solve this problem?

Direct permutations are inefficient because checking constraints for every arrangement grows factorially, while DP with bitmask tracks valid assignments efficiently.

How do I prevent double counting in overlapping hat preferences?

Update DP states in a way that each new hat only augments states for people not yet assigned, ensuring each assignment is counted exactly once.

terminal

Solution

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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]

Continue Practicing

#1349 maximum students taking exam #1595 minimum cost to connect two groups of points #1255 maximum score words formed by letters