LeetCode 1434 - Number of Ways to Wear Different Hats to Each Other

This problem asks us to count how many valid ways exist to assign hats to people under two constraints: 1. Every person

leetcodehardarraydynamic-programmingbit-manipulationbitmask

LeetCode Problem 1434

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation, Bitmask

Solution

LeetCode 1434 - Number of Ways to Wear Different Hats to Each Other

Problem Understanding

This problem asks us to count how many valid ways exist to assign hats to people under two constraints:

  1. Every person must receive exactly one hat they like.
  2. No two people may wear the same hat.

The input is a 2D array called hats.

  • hats[i] contains all hat numbers preferred by person i
  • Hat numbers range from 1 to 40
  • There are at most 10 people

The goal is to compute the total number of distinct valid assignments and return the answer modulo 10^9 + 7.

A valid assignment means:

  • Every person receives exactly one hat
  • The assigned hat belongs to that person's preference list
  • Every assigned hat is unique

For example:

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

Person 0 likes hats 3, 5, and 1.

Person 1 likes hats 3 and 5.

Valid assignments are:

(3,5)
(5,3)
(1,3)
(1,5)

So the answer is 4.

The constraints are extremely important:

  • n <= 10
  • Hat labels are limited to 40

At first glance, this looks like a bipartite matching counting problem. The important observation is that the number of people is very small, while the number of hat types is fixed at 40.

This strongly suggests using a bitmask to represent which people have already received hats.

The main edge cases include:

  • Multiple people liking the same small set of hats
  • A person having only one possible hat
  • Situations where no valid assignment exists
  • Large overlap between preferences
  • Maximum-size preference lists

A naive brute-force solution becomes infeasible because the number of assignments grows exponentially.

Approaches

Brute Force Approach

The brute-force solution tries every possible assignment of hats to people.

One way to implement this is:

  • Process people one by one
  • For each person, try every hat they like
  • Skip hats already used
  • Recursively continue until all people are assigned

This guarantees correctness because every valid assignment is explored exactly once.

However, the complexity becomes extremely large.

If each person likes many hats, we may explore roughly:

40 * 39 * 38 * ...

possibilities.

In the worst case, this becomes far too expensive.

Even though n <= 10, the branching factor is huge.

Key Insight

The critical observation is that there are only 10 people, which means we can represent assignment states using a bitmask of size 2^10.

Instead of assigning hats to people, we reverse the thinking:

  • Iterate through hats from 1 to 40
  • For each hat, decide whether to give it to one eligible person
  • Track which people already have hats using a bitmask

This transformation is powerful because:

  • The number of hats is fixed at 40
  • The number of people states is only 2^10 = 1024

This allows dynamic programming over:

(current_hat, assigned_people_mask)

The DP state represents:

How many ways can we assign hats starting from this hat number, given the current set of people already assigned hats?

This drastically reduces the search space.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(40^n) O(n) Tries all assignments recursively
Optimal O(40 × 2^n × n) O(2^n) Bitmask DP over hats

Algorithm Walkthrough

Step 1: Build Reverse Mapping

Instead of storing:

person -> hats

we build:

hat -> people

This allows us to efficiently determine which people can wear a given hat.

For example:

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

becomes:

3 -> [0]
4 -> [0,1]
5 -> [1,2]

This is useful because we process hats sequentially.

Step 2: Define the Bitmask

We use a bitmask to represent which people already have hats.

For n = 3:

mask = 101

means:

  • Person 0 has a hat
  • Person 1 does not
  • Person 2 has a hat

The final target state is:

(1 << n) - 1

which means all people have hats assigned.

Step 3: Define DP State

We define:

dp[mask]

as:

Number of ways to reach this assignment state after processing some hats.

Initially:

dp[0] = 1

because there is one way to assign no hats.

Step 4: Process Hats One by One

For every hat from 1 to 40:

  • Either skip the hat
  • Or assign it to one eligible unassigned person

We create a new DP array for each hat.

This prevents reusing the same hat multiple times in a single iteration.

Step 5: Try Assigning Current Hat

For each current mask:

  • Check every person who likes this hat

  • If that person is unassigned in the current mask:

  • Create a new mask with that person assigned

  • Add the current count into the new state

The transition looks like:

new_mask = mask | (1 << person)

Step 6: Return Final State

After processing all hats:

dp[all_people_assigned]

contains the number of valid assignments.

Return this value modulo 10^9 + 7.

Why it works

The algorithm works because every hat is processed exactly once, and every valid assignment corresponds to a unique sequence of DP transitions.

The bitmask guarantees that:

  • No person receives more than one hat
  • No hat is reused

Since every possible legal assignment is explored through DP transitions, the final count is correct.

Python Solution

from typing import List
from collections import defaultdict

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

        hat_to_people = defaultdict(list)

        for person, preferred_hats in enumerate(hats):
            for hat in preferred_hats:
                hat_to_people[hat].append(person)

        total_masks = 1 << n
        dp = [0] * total_masks
        dp[0] = 1

        for hat in range(1, 41):
            next_dp = dp[:]

            for mask in range(total_masks):
                if dp[mask] == 0:
                    continue

                for person in hat_to_people[hat]:
                    if mask & (1 << person):
                        continue

                    new_mask = mask | (1 << person)

                    next_dp[new_mask] = (
                        next_dp[new_mask] + dp[mask]
                    ) % MOD

            dp = next_dp

        return dp[total_masks - 1]

The implementation begins by constructing a reverse mapping from hats to people. This allows efficient access to all people who can wear a particular hat.

The DP array has size 2^n, where each index represents a bitmask of assigned people.

dp[mask] stores the number of ways to achieve that assignment state.

For every hat from 1 to 40, we create a copy called next_dp.

The copy is important because it ensures each hat is used at most once during transitions.

For every mask:

  • If the state count is zero, we skip it
  • Otherwise, we try assigning the current hat to every eligible unassigned person

The new assignment state is created with a bitwise OR operation.

Finally, after processing all hats, the answer is stored in the mask where all bits are set.

Go Solution

package main

func numberWays(hats [][]int) int {
	const MOD = 1000000007

	n := len(hats)

	hatToPeople := make([][]int, 41)

	for person, preferredHats := range hats {
		for _, hat := range preferredHats {
			hatToPeople[hat] = append(hatToPeople[hat], person)
		}
	}

	totalMasks := 1 << n

	dp := make([]int, totalMasks)
	dp[0] = 1

	for hat := 1; hat <= 40; hat++ {
		nextDP := make([]int, totalMasks)
		copy(nextDP, dp)

		for mask := 0; mask < totalMasks; mask++ {
			if dp[mask] == 0 {
				continue
			}

			for _, person := range hatToPeople[hat] {
				if (mask & (1 << person)) != 0 {
					continue
				}

				newMask := mask | (1 << person)

				nextDP[newMask] =
					(nextDP[newMask] + dp[mask]) % MOD
			}
		}

		dp = nextDP
	}

	return dp[totalMasks-1]
}

The Go implementation follows the same logic as the Python version.

A slice of slices is used for the reverse mapping:

hatToPeople := make([][]int, 41)

Bit operations work naturally with integers in Go.

The copy function is used to duplicate the DP array for each hat iteration.

Modulo arithmetic is performed after every update to prevent overflow.

Worked Examples

Example 1

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

Reverse Mapping

Hat People
3 [0]
4 [0,1]
5 [1,2]

Initial DP

Mask Meaning Ways
000 nobody assigned 1

Process Hat 3

Person 0 can wear it.

Old Mask New Mask Update
000 001 +1

DP becomes:

Mask Ways
000 1
001 1

Process Hat 4

Hat 4 can go to persons 0 or 1.

From mask 000:

  • assign to 0 -> 001
  • assign to 1 -> 010

From mask 001:

  • person 0 already assigned
  • assign to 1 -> 011

DP now contains:

Mask Ways
000 1
001 2
010 1
011 1

Process Hat 5

Hat 5 can go to persons 1 or 2.

Eventually we reach:

111 -> 1

Answer:

1

Example 2

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

Reverse Mapping

Hat People
1 [0]
3 [0,1]
5 [0,1]

Valid Assignments

Person 0 Person 1
3 5
5 3
1 3
1 5

Answer:

4

Example 3

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

All four people can wear any of the four hats.

This becomes counting permutations of four distinct hats among four people.

Total:

4! = 24

The DP correctly accumulates all permutations.

Complexity Analysis

Measure Complexity Explanation
Time O(40 × 2^n × n) For every hat, iterate through every mask and candidate person
Space O(2^n) DP table stores one value per mask

The number of masks is at most:

2^10 = 1024

For each of the 40 hats, we process all masks and potentially all people.

This is extremely manageable within the constraints.

Test Cases

from typing import List

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

        hat_to_people = [[] for _ in range(41)]

        for person, preferred in enumerate(hats):
            for hat in preferred:
                hat_to_people[hat].append(person)

        total_masks = 1 << n
        dp = [0] * total_masks
        dp[0] = 1

        for hat in range(1, 41):
            next_dp = dp[:]

            for mask in range(total_masks):
                if dp[mask] == 0:
                    continue

                for person in hat_to_people[hat]:
                    if mask & (1 << person):
                        continue

                    new_mask = mask | (1 << person)

                    next_dp[new_mask] = (
                        next_dp[new_mask] + dp[mask]
                    ) % MOD

            dp = next_dp

        return dp[total_masks - 1]

sol = Solution()

assert sol.numberWays([[3,4],[4,5],[5]]) == 1
# Basic valid chain assignment

assert sol.numberWays([[3,5,1],[3,5]]) == 4
# Multiple valid assignments

assert sol.numberWays([[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]) == 24
# Full permutation count

assert sol.numberWays([[1],[1]]) == 0
# Impossible because both want same single hat

assert sol.numberWays([[1],[2]]) == 1
# Simple independent assignment

assert sol.numberWays([[1,2],[2,3],[1,3]]) == 2
# Small overlapping preferences

assert sol.numberWays([[1]]) == 1
# Single person single hat

assert sol.numberWays([[1,2,3]]) == 3
# Single person many choices

assert sol.numberWays([[1,2],[1,2]]) == 2
# Two-way swapping case

assert sol.numberWays([[1,2],[1,2],[1,2]]) == 0
# Not enough unique hats

assert sol.numberWays([[1,2,3],[1,2,3],[1,2,3]]) == 6
# Permutations of 3 hats among 3 people

Test Summary

Test Why
[[3,4],[4,5],[5]] Validates basic sequential assignment
[[3,5,1],[3,5]] Tests multiple valid combinations
[[1,2,3,4], ...] Tests permutation-heavy case
[[1],[1]] Tests impossible assignment
[[1],[2]] Tests simplest valid assignment
[[1,2],[2,3],[1,3]] Tests overlapping preferences
[[1]] Smallest possible input
[[1,2,3]] Single person with many hats
[[1,2],[1,2]] Tests symmetric assignments
[[1,2],[1,2],[1,2]] Tests insufficient unique hats
[[1,2,3],[1,2,3],[1,2,3]] Tests factorial-style counting

Edge Cases

Multiple People Want the Same Single Hat

Consider:

[[1],[1]]

Both people only like hat 1.

Since hats must be unique, only one person can receive the hat.

No valid assignment exists.

A naive implementation may accidentally count invalid duplicate assignments. The bitmask DP prevents this because once a hat is assigned, the transition only updates one new state.

A Person Has Many Choices

Consider:

[[1,2,3,4,5]]

There is only one person, but many acceptable hats.

The algorithm correctly counts each hat as a separate valid assignment because every transition from the empty mask produces a unique final state.

Not Enough Unique Hats

Consider:

[[1,2],[1,2],[1,2]]

There are three people but only two distinct hats.

Even though everyone has preferences, it is impossible to assign unique hats to all people.

The DP naturally handles this because the final full-assignment mask is never reached.

Large Preference Overlap

Consider:

[[1,2,3],[1,2,3],[1,2,3]]

Every person likes the same hats.

This creates many overlapping recursive possibilities.

A brute-force DFS would repeatedly recompute similar states.

The DP avoids recomputation because every assignment state is represented once by its bitmask.