<p>There are <code>n</code> people and <code>40</code> types of hats labeled from <code>1</code> to <code>40</code>.</p>

<p>Given a 2D integer array <code>hats</code>, where <code>hats[i]</code> is a list of all hats preferred by the <code>i<sup>th</sup></code> person.</p>

<p>Return <em>the number of ways that the <code>n</code> people wear different hats to each other</em>.</p>

<p>Since the answer may be too large, return it modulo <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> hats = [[3,5,1],[3,5]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are 4 ways to choose hats:
(3,5), (5,3), (1,3) and (1,5)
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
<strong>Output:</strong> 24
<strong>Explanation:</strong> Each person can choose hats labeled from 1 to 4.
Number of Permutations of (1,2,3,4) = 24.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == hats.length</code></li>
	<li><code>1 &lt;= n &lt;= 10</code></li>
	<li><code>1 &lt;= hats[i].length &lt;= 40</code></li>
	<li><code>1 &lt;= hats[i][j] &lt;= 40</code></li>
	<li><code>hats[i]</code> contains a list of <strong>unique</strong> integers.</li>
</ul>

class Solution {
public:
    int mod = 1e9 + 7;
    int numberWays(vector<vector<int>>& hats) {
        int n = hats.size();
        unordered_map<int, vector<int>> hats_to_people_map;
        for(int ppl_idx = 0; ppl_idx < n; ++ppl_idx) {
            for(int& hat : hats[ppl_idx]) {
                hats_to_people_map[hat].push_back(ppl_idx);
            }
        }
        vector<int> distinct_hats;
        for(auto& entry : hats_to_people_map) {
            distinct_hats.push_back(entry.first);
        }
        vector<vector<int>> memo(distinct_hats.size(), vector<int>((1 << n), -1));
        return pickPeopleForEachHat(0, 0, memo, hats_to_people_map, distinct_hats, (1 << n) - 1);
    }

    int pickPeopleForEachHat(int idx, int mask, vector<vector<int>>& memo, unordered_map<int, vector<int>>& hats_to_people_map, vector<int>& hats, const int& total_num_people) {
        if(idx >= hats.size()) {
            if(total_num_people == mask) return 1;
            return 0;
        }

        // If we have processed this subproblem before we can return the result.
        if(memo[idx][mask] != -1) return memo[idx][mask];

        int total_ways = pickPeopleForEachHat(idx + 1, mask, memo, hats_to_people_map, hats, total_num_people);
        for(int& person : hats_to_people_map[hats[idx]]) {
            // If this person was previously selected we can continue;
            if((mask | (1 << person)) == mask) continue;

            int new_mask = (mask | (1 << person));

            total_ways += pickPeopleForEachHat(idx + 1, new_mask, memo, hats_to_people_map, hats, total_num_people);

            total_ways %= mod;
        }
        return  memo[idx][mask] = total_ways;
    }
};

/*
    For every person we can we try every hat that person can wear 
        long long int mask to determine if a hat is being worn.
        Eventually if we finish the last person we can return 1.

    For every iteration we can check if we have seen this mask before 

    If there is 10 people and 40 hats, for each hat we either pick this hat or not so there is 2^40 combinations. 
    Across 10 people that would be 10 * 2^ 40 which is very large

    The other alternative is flip people and hats. Where for each hat we are try to pick this person or no pick this person.
    The difference here is now if there is 10 people to pick or not we now have 2^10 combinations. Across 40 hats that is
    40 * 2^10 combinations which is significantly smaller than 10*2^40.
*/

// 
13600