# Number of Ways to Wear Different Hats to Each Other
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-ways-to-wear-different-hats-to-each-other)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-wear-different-hats-to-each-other
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
**Companies:** [Mindtickle](https://scaleengineer.com/companies/mindtickle)
---
## Problem
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 `ith` person.

Return the number of ways that `n` people can wear **different** hats from each other.

Since the answer may be too large, return it modulo `109 + 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.

# Approaches
## Brute-Force Backtracking
This approach uses a standard backtracking algorithm to explore all possible ways of assigning hats to people. We try to assign a hat to each person one by one, from person 0 to person `n-1`. For each person, we iterate through their list of preferred hats. If a hat is not already worn by someone else, we assign it to the current person and recursively move on to the next person. If we successfully assign hats to all `n` people, we count it as one valid way.
**Time:** O(n! * C) · **Space:** O(n + num_hats)
**Pros:** Simple to understand and conceptualize.
**Cons:** Extremely inefficient and will time out for the given constraints.; The state space for memoization `(person, used_hats_mask)` would be `n * 2^40`, which is too large to fit in memory, preventing a straightforward DP optimization of this approach.
### Explanation
The core idea is to build a valid assignment person by person. We maintain the state using two parameters: the index of the person we are currently considering (`personIndex`) and a bitmask (`usedHatsMask`) to keep track of which hats have already been assigned. The recursion explores every possible branch of assignments. While simple to conceptualize, this method suffers from a massive number of redundant computations and an explosive number of states. For example, the arrangement of hats for the first `k` people will be recomputed for every different arrangement of hats for the people before them. Due to the constraints (`n` up to 10, hats up to 40), the number of paths to explore is prohibitively large, leading to a 'Time Limit Exceeded' error on most platforms.
### Algorithm
1. Define a recursive function, say `solve(personIndex, usedHatsMask)`, which calculates the number of ways to assign hats to people from `personIndex` to `n-1`, given that the hats represented by `usedHatsMask` are already taken.
2. **Base Case:** If `personIndex` equals `n`, it means we have successfully assigned a unique hat to all `n` people. Return 1, as this represents one valid assignment.
3. **Recursive Step:** For the current `personIndex`, iterate through all the hats `h` that this person prefers (from `hats[personIndex]`).
4. For each preferred hat `h`, check if it has already been used by examining the `h`-th bit in `usedHatsMask`.
5. If the hat `h` is not used, make a recursive call: `solve(personIndex + 1, usedHatsMask | (1 << h))`. This explores assigning hat `h` to the current person and moving to the next person.
6. Sum the results from all valid recursive calls to get the total number of ways for the current state.
7. The initial call to the function would be `solve(0, 0)`.

## Dynamic Programming with Memoization (Hat-centric)
This approach uses dynamic programming with memoization to solve the problem efficiently. The crucial observation is that the state space becomes manageable if we iterate through the hats instead of the people. The state of our DP is defined by `(hatId, personMask)`, which represents the number of ways to assign hats from `hatId` to 40 to a specific subset of people who are not yet covered by the `personMask`.

By processing hats one by one, we decide for each hat whether to assign it to an eligible person or to skip it. This avoids the large state space issue of the brute-force approach and effectively solves the problem within the time limits.
**Time:** O(num_hats * 2^n * n) · **Space:** O(num_hats * 2^n)
**Pros:** Efficient enough to pass the given constraints.; Systematically avoids re-computation of subproblems through memoization.
**Cons:** Requires a significant amount of memory for the DP table, `O(num_hats * 2^n)`.
### Explanation
First, we preprocess the input `hats` list to create an inverted index, `peopleByHat`, where `peopleByHat[h]` contains a list of people who like hat `h`. This makes it easy to find candidates for each hat.

We then define a recursive function `solve(hatId, mask)` that computes the number of ways to assign hats from `hatId` onwards, given that the people represented by `mask` have already been assigned hats. The results are stored in a `dp` table to avoid recomputing for the same state `(hatId, mask)`.

The recursion explores two main possibilities for each hat: either we don't use it and move to the next hat, or we assign it to one of the people who prefer it and don't have a hat yet. The final answer is the result of the initial call `solve(1, 0)`.

```java
class Solution {
    int MOD = 1_000_000_007;
    List<Integer>[] peopleByHat;
    int n;
    int allMask;
    Integer[][] dp;

    public int numberWays(List<List<Integer>> hats) {
        this.n = hats.size();
        this.allMask = (1 << n) - 1;
        this.peopleByHat = new ArrayList[41];
        for (int i = 0; i <= 40; i++) {
            peopleByHat[i] = new ArrayList<>();
        }

        for (int i = 0; i < n; i++) {
            for (int hat : hats.get(i)) {
                peopleByHat[hat].add(i);
            }
        }

        this.dp = new Integer[41][1 << n];
        return solve(1, 0);
    }

    private int solve(int hatId, int mask) {
        if (mask == allMask) {
            return 1;
        }
        if (hatId > 40) {
            return 0;
        }
        if (dp[hatId][mask] != null) {
            return dp[hatId][mask];
        }

        // Option 1: Don't use the current hat
        long ways = solve(hatId + 1, mask);

        // Option 2: Use the current hat for an eligible person
        for (int person : peopleByHat[hatId]) {
            if ((mask & (1 << person)) == 0) {
                ways = (ways + solve(hatId + 1, mask | (1 << person))) % MOD;
            }
        }

        return dp[hatId][mask] = (int) ways;
    }
}
```
### Algorithm
1. **Preprocessing:** The key insight is to change the perspective from assigning hats to people to assigning people to hats. Create a mapping from each hat ID to a list of people who prefer that hat. Let's call this `peopleByHat`.
2. **DP State:** Define a recursive function `solve(hatId, personMask)` with memoization. `hatId` is the current hat we are considering (from 1 to 40), and `personMask` is a bitmask representing the set of people who have already been assigned a hat.
3. **Memoization:** Use a 2D array, `dp[hatId][personMask]`, to store the results of subproblems to avoid re-computation.
4. **Base Cases:**
   - If `personMask` indicates all people have a hat (`personMask == (1 << n) - 1`), we have found a valid assignment. Return 1.
   - If `hatId` exceeds 40 and not all people have hats, it's impossible to complete the assignment. Return 0.
5. **Recursive Step:** For the state `(hatId, personMask)`, we have two choices for `hatId`:
   - **Don't use `hatId`:** The number of ways is `solve(hatId + 1, personMask)`.
   - **Use `hatId`:** Iterate through the list of people `p` who prefer `hatId` (from `peopleByHat[hatId]`). If person `p` has not yet been assigned a hat (i.e., the `p`-th bit in `personMask` is 0), we can assign `hatId` to them. The number of ways for this choice is `solve(hatId + 1, personMask | (1 << p))`. Sum these up for all such people `p`.
6. The total ways for the current state is the sum of ways from both choices. Store this result in `dp[hatId][personMask]` before returning.

## Space-Optimized Bottom-Up Dynamic Programming
This approach is a space-optimized version of the hat-centric dynamic programming solution. Instead of using a 2D DP table, we use a 1D array of size `2^n`. The state `dp[mask]` represents the number of ways to assign hats to the people represented by `mask` using the hats considered so far.

We iterate through each hat from 1 to 40. For each hat, we update the `dp` array based on the possibilities this new hat introduces. By iterating through the masks in a specific order (from largest to smallest), we can perform the updates in-place, effectively reducing the space complexity from `O(num_hats * 2^n)` to `O(2^n)` while keeping the time complexity the same.
**Time:** O(num_hats * 2^n * n) · **Space:** O(2^n)
**Pros:** Most memory-efficient solution.; Iterative nature can sometimes have less overhead than recursion.; Same time efficiency as the top-down DP approach.
**Cons:** The logic for the in-place update (iterating masks in reverse) can be less intuitive than a top-down recursive approach.
### Explanation
The bottom-up approach builds the solution iteratively. We start with a `dp` array where `dp[0] = 1` and all other `dp[mask] = 0`. This represents the base case: with zero hats, there's one way to cover zero people.

We then loop through each hat `h` from 1 to 40. In each iteration, we calculate the new `dp` states after considering hat `h`. The new value for `dp[mask]` is the old `dp[mask]` (representing ways without using hat `h`) plus the sum of ways for states where hat `h` is assigned to a person in the mask. Specifically, for each person `p` in `mask` who likes hat `h`, we add `dp[mask ^ (1 << p)]` to `dp[mask]`. This `dp[mask ^ (1 << p)]` represents the number of ways the smaller group of people could be formed with previous hats.

To perform this update using a single `dp` array, we iterate the masks in reverse. This ensures that when we calculate `dp[mask]`, the values for smaller masks `dp[mask ^ (1 << p)]` have not yet been updated for the current hat `h`, so they correctly reflect the state from the previous iteration (`h-1`).

```java
class Solution {
    int MOD = 1_000_000_007;

    public int numberWays(List<List<Integer>> hats) {
        int n = hats.size();
        List<Integer>[] peopleByHat = new ArrayList[41];
        for (int i = 0; i <= 40; i++) {
            peopleByHat[i] = new ArrayList<>();
        }

        for (int i = 0; i < n; i++) {
            for (int hat : hats.get(i)) {
                peopleByHat[hat].add(i);
            }
        }

        int[] dp = new int[1 << n];
        dp[0] = 1;

        for (int h = 1; h <= 40; h++) {
            for (int mask = (1 << n) - 1; mask >= 0; mask--) {
                for (int person : peopleByHat[h]) {
                    if ((mask & (1 << person)) != 0) {
                        int prevMask = mask ^ (1 << person);
                        dp[mask] = (dp[mask] + dp[prevMask]) % MOD;
                    }
                }
            }
        }

        return dp[(1 << n) - 1];
    }
}
```
### Algorithm
1. **Preprocessing:** As with the top-down approach, create the `peopleByHat` mapping.
2. **DP State:** Use a 1D array `dp` of size `2^n`. `dp[mask]` will store the number of ways to assign hats (up to the one currently being processed) to the set of people represented by `mask`.
3. **Initialization:** Initialize `dp[0] = 1`, signifying one way to assign hats to zero people (by doing nothing). All other `dp` entries are 0.
4. **Iteration:** Iterate through each hat `h` from 1 to 40.
5. For each hat, we update the `dp` array. To do this correctly in-place, we iterate through the masks `m` from `(1 << n) - 1` down to 0.
6. **Transition:** For each mask `m`, we consider assigning the current hat `h` to any eligible person `p` within that mask. An eligible person `p` is one who prefers hat `h` and is represented in the mask `m`.
7. If person `p` is in mask `m`, it means we can form the assignment for `m` by giving hat `h` to `p`, and having the remaining people (`m` without `p`, i.e., `m ^ (1 << p)`) assigned hats from the previous set (1 to `h-1`).
8. The number of ways to do this is `dp[m ^ (1 << p)]`. We add this to `dp[m]`. The update rule is `dp[m] = (dp[m] + dp[m ^ (1 << p)]) % MOD`.
9. The reverse iteration over masks is crucial. It ensures that when we compute `dp[m]`, the value `dp[m ^ (1 << p)]` (where `m ^ (1 << p) < m`) is from the previous state (before considering hat `h`).
10. **Result:** After iterating through all 40 hats, the final answer is `dp[(1 << n) - 1]`, which represents the number of ways to assign hats to all `n` people.

# Solutions
### Java

```java
class Solution {
public
  int numberWays(List<List<Integer>> hats) {
    int n = hats.size();
    int m = 0;
    for (var h : hats) {
      for (int v : h) {
        m = Math.max(m, v);
      }
    }
    List<Integer>[] g = new List[m + 1];
    Arrays.setAll(g, k->new ArrayList<>());
    for (int i = 0; i < n; ++i) {
      for (int v : hats.get(i)) {
        g[v].add(i);
      }
    }
    final int mod = (int)1 e9 + 7;
    int[][] f = new int[m + 1][1 << n];
    f[0][0] = 1;
    for (int i = 1; i <= m; ++i) {
      for (int j = 0; j < 1 << n; ++j) {
        f[i][j] = f[i - 1][j];
        for (int k : g[i]) {
          if ((j >> k & 1) == 1) {
            f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod;
          }
        }
      }
    }
    return f[m][(1 << n) - 1];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberWays(vector<vector<int>> &hats) {
    int n = hats.size();
    int m = 0;
    for (auto &h : hats) {
      m = max(m, *max_element(h.begin(), h.end()));
    }
    vector<vector<int>> g(m + 1);
    for (int i = 0; i < n; ++i) {
      for (int &v : hats[i]) {
        g[v].push_back(i);
      }
    }
    const int mod = 1e9 + 7;
    int f[m + 1][1 << n];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 1; i <= m; ++i) {
      for (int j = 0; j < 1 << n; ++j) {
        f[i][j] = f[i - 1][j];
        for (int k : g[i]) {
          if (j >> k & 1) {
            f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod;
          }
        }
      }
    }
    return f[m][(1 << n) - 1];
  }
};

```

### Python

```python
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]

```