#1434 Number of Ways to Wear Different Hats to Each Other - Solution

There are n people and 40 types of hats labeled from 1 to 40.

Given a 2D integer array hats, where hats[i] is a list of all hats preferred by the i^th person.

Return the number of ways that the n people wear different hats to each other.

Since the answer may be too large, return it modulo 10⁹ + 7.

Example 1:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: 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
Explanation: 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
Explanation: 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.

This problem can be solved efficiently using Dynamic Programming with Bitmasking. Since the number of people is small (at most 10) but the number of hats can go up to 40, the key idea is to track which people have already been assigned hats using a bitmask. Each bit in the mask represents whether a specific person already has a hat.

First, build a mapping from each hat to the list of people who can wear it. Then iterate over hats one by one and update a DP state dp[mask], where mask represents the set of people who have already received hats. For every hat, you can either skip it or assign it to one of the eligible people whose bit is not yet set in the mask.

The transitions accumulate the number of valid assignments while ensuring that each person receives exactly one unique hat. The final result corresponds to the mask where all people are assigned hats. Use modulo 1e9+7 to avoid overflow.

This approach keeps the state space manageable by leveraging the small number of people.

Approach	Time Complexity	Space Complexity
Dynamic Programming with Bitmask (Hat Iteration)	O(40 * 2^n * n)	O(2^n)

Solutions (4)

Backtracking with Memoization

This approach involves using backtracking to try all possible assignments of hats by recursively assigning hats to people.

We use memoization to store already computed results to avoid redundant calculations, improving efficiency.

Time Complexity: O(2^n * 40) where `n` is the number of people.

Space Complexity: O(2^n * 40) due to memoization storage.

Python JavaScript

1MOD = 10**9 + 7
2
3def number_ways(hats):
4    n = len(hats)
5    all_mask = (1 << n) - 1
6    dp = {}
7    hat_to_people = [[] for _ in range(41)]
8    for person, hat_list in enumerate(hats):
9        for hat in hat_list:
10            hat_to_people[hat].append(person)
11    
12    def ways(hat, mask):
13        if mask == all_mask:
14            return 1
15        if hat > 40:
16            return 0
17        if (hat, mask) in dp:
18            return dp[(hat, mask)]
19        ans = ways(hat + 1, mask)
20        for person in hat_to_people[hat]:
21            if mask & (1 << person) == 0:
22                ans += ways(hat + 1, mask | (1 << person))
23                ans %= MOD
24        dp[(hat, mask)] = ans
25        return ans
26    
27    return ways(1,0)

Explanation

We implemented a `ways` function that checks each hat number iteratively and recursively assigns it to available people.

Using a bit mask helps track which people have already been assigned hats.

Memoization is employed to cache results of previously computed states.

Dynamic Programming with Bitmasking

We use dynamic programming and bitmasking to efficiently calculate the number of distinct hat placements.

Each state is represented by a bitmask indicating which people have been assigned hats.

Transition between states occurs by considering each hat for each person who prefers it.

Time Complexity: O(2^n * 40)

Space Complexity: O(2^n * 40)

C++Java

1#include <vector>
2#include <unordered_map>
3
4using namespace std;
5#define MOD 1000000007

int numberOfWays(vector<vector<int>>& hats) {
    int n = hats.size();
    vector<vector<int>> people_with_hat(41);
    for (int i = 0; i < n; ++i) {
        for (int hat : hats[i]) {
            people_with_hat[hat].push_back(i);
        }
    }
    unordered_map<int, int> dp;
    return dfs(0, 0, people_with_hat, dp, n);
}

int dfs(int hat, int mask, vector<vector<int>>& people_with_hat, unordered_map<int, int>& dp, int n) {
    if (mask == (1 << n) - 1) return 1;
    if (hat > 40) return 0;
    if (dp.count((hat << 10) | mask)) return dp[(hat << 10) | mask];
    int ans = dfs(hat + 1, mask, people_with_hat, dp, n);
    for (int person : people_with_hat[hat]) {
        if (!(mask & (1 << person))) {
            ans = (ans + dfs(hat + 1, mask | (1 << person), people_with_hat, dp, n)) % MOD;
        }
    }
    dp[(hat << 10) | mask] = ans;
    return ans;
}