> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/number-of-ways-to-wear-different-hats-to-each-other.md).

# Number of Ways to Wear Different Hats to Each Other

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

Given a list of list of integers `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^9 + 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.
```

**Example 4:**

```
Input: hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]]
Output: 111
```

**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.

```java
/**
 * The first idea come to our mind is that we will do straightforward like the
 * problem said: Return the number of ways that the n people wear different hats
 * to each other. We will assign n people with different hats and use dp to
 * calculate number of ways.
 */
// But that will result in TLE
class Solution {
    int mod = 1_000_000_007;

    public int numberWays(List<List<Integer>> hats) {
        int n = hats.size();
        // h2p[i] indicates the list of people who can wear i_th hat
        List<Integer>[] h2p = new List[41];
        for (int i = 1; i <= 40; i++)
            h2p[i] = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int hat : hats.get(i))
                h2p[hat].add(i);
        // max value of full mask can be 2^n -> 1024
        Integer[][] dp = new Integer[41][1024];
        // Using a bitmask where each bit shows whether the ith perseon has been
        // assigned or not
        return dfs(h2p, (1 << n) - 1, 1, 0, dp);
        // we are using 2 masks here
        // 1st-> (1<<n)-1 -> this shows the final mask configuration we want to reach
        // 2nd-> 0 -> this shows the current mask configuration
    }

    // dp[i][j] -> ways to assign ith hat to mask value of j
    // Remember that (i+1)th hat will be assigned after the ith hat
    int dfs(List<Integer>[] h2p, int allMask, int hat, int assignedPeople, Integer[][] dp) {
        if (assignedPeople == allMask)
            return 1; // Check if assigned different hats to all people
        if (hat > 40)
            return 0; // no more hats to process
        if (dp[hat][assignedPeople] != null)
            return dp[hat][assignedPeople];
        int ans = dfs(h2p, allMask, hat + 1, assignedPeople, dp); // Don't wear this hat
        for (int p : h2p[hat]) {
            // Skip if person `p` was assigned hat
            if (((assignedPeople >> p) & 1) == 1)
                continue;
            // Wear this hat for p_th person
            ans += dfs(h2p, allMask, hat + 1, assignedPeople | (1 << p), dp);
            ans %= mod;
        }
        dp[hat][assignedPeople] = ans;
        return ans;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/number-of-ways-to-wear-different-hats-to-each-other.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.