Problem Description

You are given n people and a list of hats, where each person has a list of hats they are willing to wear. There are 40 different hats, labeled from 1 to 40. Each person may have a subset of these hats they like.

The goal is to determine the number of ways to assign hats to people such that:

• Each person wears exactly one hat from their list of preferred hats.
• No two people wear the same hat (all hats assigned are unique).

Key constraints:

• Each person must get exactly one hat.
• No hat is worn by more than one person.
• You cannot reuse hats.
• The number of people is small (up to 10), but the number of hats is large (always 40).

Thought Process

At first glance, you might consider generating all possible assignments of hats to people and checking which ones are valid. However, since there are up to 40 hats and each person can have many choices, this approach quickly becomes infeasible due to the combinatorial explosion.

Instead, notice:

• The number of people (n) is small (≤ 10), but the number of hats is fixed (40).
• It's easier to think in terms of hats: for each hat, decide whether to assign it (and to whom), or skip it.
• We need to ensure that each person gets exactly one hat, and no hat is reused.

Solution Approach

We'll use dynamic programming with bitmasking to efficiently represent assignment states.

1. State Representation:
   • Let mask be a bitmask of length n (number of people), where the i-th bit is 1 if person i has been assigned a hat.
   • Let dp[mask][hat] represent the number of ways to assign hats 1..hat such that the assignment matches the current mask.
2. Transition:
   • For each hat, for each possible assignment of that hat to a person (if that person likes the hat and hasn't been assigned yet), update the DP state.
   • For each DP state, you can either skip the current hat (carry over the previous value) or assign it to a person who likes it and update the mask accordingly.
3. Initialization:
   • dp[0][0] = 1: zero people assigned, zero hats considered.
4. Result:
   • The answer is dp[FULL_MASK][40], where FULL_MASK means all people have been assigned hats.
5. Optimization:
   • Since the number of people is small, we can use bitmasking for people (up to 2^10 = 1024 states).
   • We process hats one by one, trying all possible assignments at each step.
6. Preprocessing:
   • For each hat, keep a list of people who like it (reverse mapping).

Example Walkthrough

Suppose there are 2 people:

• Person 0 likes hats [1, 2, 3]
• Person 1 likes hats [3, 4]

1. Start with mask = 0b00 (no one assigned).
2. Consider hat 1: only person 0 likes it. Assigning hat 1 to person 0 gives mask = 0b01.
3. Hat 2: only person 0 likes it. Assigning hat 2 to person 0 gives mask = 0b01 (another way).
4. Hat 3: both people like it.
   • Assign to person 0: mask = 0b01
   • Assign to person 1: mask = 0b10
5. Hat 4: only person 1 likes it. Assign to person 1: mask = 0b10
6. Continue propagating DP states, updating the number of ways for each mask as hats are assigned.
7. At the end, mask = 0b11 (both assigned) gives the total number of valid assignments.

In this case, the valid assignments are:

• Person 0: 1, Person 1: 3
• Person 0: 2, Person 1: 3
• Person 0: 3, Person 1: 4

Time and Space Complexity

Brute-force:

• There are up to 40 hats and n people, so the number of possible assignments is up to 40!/(40-n)! (huge for n > 5).
• Checking all permutations is not feasible.

• There are 2^n possible masks (states for people assigned hats).
• For each hat (40), we process all masks. For each mask, we try assigning the hat to each person who likes it.
• Time complexity: O(40 * 2^n * n) where n ≤ 10, so this is about 40 * 1024 * 10 = 409,600 operations (very efficient).
• Space complexity: O(2^n) for the DP table.

Summary

By leveraging the small number of people and the fixed number of hats, we use dynamic programming with bitmasking to efficiently count the number of valid assignments. The key insight is to process hats one by one, updating assignment states, and using bitmasks to represent which people have already been assigned hats. This approach is both elegant and computationally efficient, avoiding the pitfalls of brute-force enumeration.

Code Implementation

MOD = 10**9 + 7

class Solution:
    def numberWays(self, hats):
        n = len(hats)
        hat_to_people = [[] for _ in range(41)]
        for person, hat_list in enumerate(hats):
            for h in hat_list:
                hat_to_people[h].append(person)
        dp = [0] * (1 << n)
        dp[0] = 1
        for hat in range(1, 41):
            ndp = dp[:]
            for mask in range(1 << n):
                if dp[mask] == 0:
                    continue
                for person in hat_to_people[hat]:
                    if not (mask & (1 << person)):
                        ndp[mask | (1 << person)] = (ndp[mask | (1 << person)] + dp[mask]) % MOD
            dp = ndp
        return dp[(1 << n) - 1]
      

#define MOD 1000000007
class Solution {
public:
    int numberWays(vector<vector<int>>& hats) {
        int n = hats.size();
        vector<vector<int>> hat_to_people(41);
        for (int i = 0; i < n; ++i) {
            for (int h : hats[i]) {
                hat_to_people[h].push_back(i);
            }
        }
        vector<int> dp(1 << n, 0);
        dp[0] = 1;
        for (int hat = 1; hat <= 40; ++hat) {
            vector<int> ndp = dp;
            for (int mask = 0; mask < (1 << n); ++mask) {
                if (dp[mask] == 0) continue;
                for (int person : hat_to_people[hat]) {
                    if (!(mask & (1 << person))) {
                        ndp[mask | (1 << person)] = (ndp[mask | (1 << person)] + dp[mask]) % MOD;
                    }
                }
            }
            dp = ndp;
        }
        return dp[(1 << n) - 1];
    }
};
      

class Solution {
    static final int MOD = 1000000007;
    public int numberWays(List<List<Integer>> hats) {
        int n = hats.size();
        List<List<Integer>> hatToPeople = new ArrayList<>();
        for (int i = 0; i <= 40; ++i) hatToPeople.add(new ArrayList<>());
        for (int i = 0; i < n; ++i) {
            for (int h : hats.get(i)) {
                hatToPeople.get(h).add(i);
            }
        }
        int[] dp = new int[1 << n];
        dp[0] = 1;
        for (int hat = 1; hat <= 40; ++hat) {
            int[] ndp = dp.clone();
            for (int mask = 0; mask < (1 << n); ++mask) {
                if (dp[mask] == 0) continue;
                for (int person : hatToPeople.get(hat)) {
                    if ((mask & (1 << person)) == 0) {
                        ndp[mask | (1 << person)] = (ndp[mask | (1 << person)] + dp[mask]) % MOD;
                    }
                }
            }
            dp = ndp;
        }
        return dp[(1 << n) - 1];
    }
}
      

const MOD = 1e9 + 7;
var numberWays = function(hats) {
    const n = hats.length;
    const hatToPeople = Array.from({length: 41}, () => []);
    for (let i = 0; i < n; ++i) {
        for (const h of hats[i]) {
            hatToPeople[h].push(i);
        }
    }
    let dp = new Array(1 << n).fill(0);
    dp[0] = 1;
    for (let hat = 1; hat <= 40; ++hat) {
        let ndp = dp.slice();
        for (let mask = 0; mask < (1 << n); ++mask) {
            if (dp[mask] == 0) continue;
            for (const person of hatToPeople[hat]) {
                if ((mask & (1 << person)) === 0) {
                    ndp[mask | (1 << person)] = (ndp[mask | (1 << person)] + dp[mask]) % MOD;
                }
            }
        }
        dp = ndp;
    }
    return dp[(1 << n) - 1];
};