## Approach 1: Top-down

• Time:O(40 \cdot 2^n \cdot n), where n = |\texttt{hats}|
• Space:O(40 \cdot 2^n)

## C++

class Solution {
public:
int numberWays(vector<vector<int>>& hats) {
constexpr int nHats = 40;
const int nPeople = hats.size();
hatToPeople.resize(nHats + 1);
// dp[i][j] := # of ways to assign hats 1, 2, ..., i to people in mask j
dp.resize(nHats + 1, vector<int>(1 << nPeople, -1));

for (int i = 0; i < nPeople; ++i)
for (const int hat : hats[i])
hatToPeople[hat].push_back(i);

return ways(hats, 0, 1);
}

private:
constexpr static int kMod = 1e9 + 7;
vector<vector<int>> hatToPeople;
vector<vector<int>> dp;

int ways(const vector<vector<int>>& hats, int assignment, int h) {
// all people are assigned
if (assignment == (1 << hats.size()) - 1)
return 1;
if (h > 40)
return 0;
if (dp[h][assignment] != -1)
return dp[h][assignment];

// don't wear hat h
int ans = ways(hats, assignment, h + 1);

for (const int p : hatToPeople[h]) {
// person p was assigned hat h before
if (assignment & 1 << p)
continue;

// assigned hat h to person p
ans += ways(hats, assignment | 1 << p, h + 1);
ans %= kMod;
}

return dp[h][assignment] = ans;
}
};


## JAVA

class Solution {
public int numberWays(List<List<Integer>> hats) {
final int nHats = 40;
final int nPeople = hats.size();
hatToPeople = new List[nHats + 1];
// dp[i][j] := # of ways to assign hats 1, 2, ..., i to people in mask j
dp = new Integer[nHats + 1][1 << nPeople];

for (int i = 1; i <= nHats; ++i)
hatToPeople[i] = new ArrayList<>();

for (int i = 0; i < nPeople; ++i)
for (final int hat : hats.get(i))

return ways(hats, 0, 1);
}

private static final int kMod = (int) 1e9 + 7;
private List<Integer>[] hatToPeople;
private Integer[][] dp;

private int ways(List<List<Integer>> hats, int assignment, int h) {
// all people are assigned
if (assignment == (1 << hats.size()) - 1)
return 1;
if (h > 40)
return 0;
if (dp[h][assignment] != null)
return dp[h][assignment];

// don't wear hat h
int ans = ways(hats, assignment, h + 1);

for (final int p : hatToPeople[h]) {
// person p was assigned hat h before
if ((assignment & 1 << p) > 0)
continue;

// assigned hat h to person p
ans += ways(hats, assignment | 1 << p, h + 1);
ans %= kMod;
}

return dp[h][assignment] = ans;
}
}


## Approach 2: Bottom-up 2D DP

• Time:O(40 \cdot 2^n \cdot n)
• Space:O(40 \cdot 2^n)

## C++

class Solution {
public:
int numberWays(vector<vector<int>>& hats) {
constexpr int kMod = 1e9 + 7;
constexpr int nHats = 40;
const int nPeople = hats.size();
const int nAssignments = 1 << nPeople;
vector<vector<int>> hatToPeople(nHats + 1);
// dp[i][j] := # of ways to assign hats 1, 2, ..., i to people in mask j
vector<vector<int>> dp(nHats + 1, vector<int>(nAssignments));
dp[0][0] = 1;

for (int i = 0; i < nPeople; ++i)
for (const int hat : hats[i])
hatToPeople[hat].push_back(i);

for (int h = 1; h <= nHats; ++h)
// for each assignment j of people
for (int j = 0; j < nAssignments; ++j) {
// we can cover the assignment j in 2 ways
// (1) by first h - 1 hats (i.e., w/o hat h)
dp[h][j] += dp[h - 1][j];
dp[h][j] %= kMod;
for (const int p : hatToPeople[h])
if (j & 1 << p) {
// (2) by first h - 1 hats assigned to people w/o person p and
//     hat h assigned to person p
dp[h][j] += dp[h - 1][j ^ 1 << p];
dp[h][j] %= kMod;
}
}

return dp[nHats][nAssignments - 1];
}
};


## JAVA

class Solution {
public int numberWays(List<List<Integer>> hats) {
final int kMod = (int) 1e9 + 7;
final int nHats = 40;
final int nPeople = hats.size();
final int nAssignments = 1 << nPeople;
List<Integer>[] hatToPeople = new List[nHats + 1];
// dp[i][j] := # of ways to assign hats 1, 2, ..., i to people in mask j
int[][] dp = new int[nHats + 1][nAssignments];
dp[0][0] = 1;

for (int i = 1; i <= nHats; ++i)
hatToPeople[i] = new ArrayList<>();

for (int i = 0; i < nPeople; ++i)
for (final int hat : hats.get(i))

for (int h = 1; h <= nHats; ++h)
// for each assignment j of people
for (int j = 0; j < nAssignments; ++j) {
// we can cover the assignment j in 2 ways:
// (1) by first h - 1 hats (i.e., w/o hat h)
dp[h][j] += dp[h - 1][j];
dp[h][j] %= kMod;
for (final int p : hatToPeople[h])
if ((j & 1 << p) > 0) {
// (2) by first h - 1 hats assigned to people w/o person p and
//     hat h assigned to person p
dp[h][j] += dp[h - 1][j ^ 1 << p];
dp[h][j] %= kMod;
}
}

return dp[nHats][nAssignments - 1];
}
}


## Approach 3: Bottom-up 1D DP

• Time:O(40 \cdot 2^n \cdot n)
• Space:O(2^n)

## C++

class Solution {
public:
int numberWays(vector<vector<int>>& hats) {
constexpr int kMod = 1e9 + 7;
constexpr int nHats = 40;
const int nPeople = hats.size();
const int nAssignments = 1 << nPeople;
vector<vector<int>> hatToPeople(nHats + 1);
// dp[i] := # of ways to assign hats so far to people in mask i
vector<int> dp(nAssignments);
dp[0] = 1;

for (int i = 0; i < nPeople; ++i)
for (const int hat : hats[i])
hatToPeople[hat].push_back(i);

for (int h = 1; h <= nHats; ++h)
for (int j = nAssignments - 1; j >= 0; --j)
for (const int p : hatToPeople[h])
if (j & 1 << p) {
dp[j] += dp[j ^ 1 << p];
dp[j] %= kMod;
}

return dp[nAssignments - 1];
}
};


## JAVA

class Solution {
public int numberWays(List<List<Integer>> hats) {
final int kMod = (int) 1e9 + 7;
final int nHats = 40;
final int nPeople = hats.size();
final int nAssignments = 1 << nPeople;
List<Integer>[] hatToPeople = new List[nHats + 1];
// dp[i] := # of ways to assign hats so far to people in mask i
int[] dp = new int[nAssignments];
dp[0] = 1;

for (int i = 1; i <= nHats; ++i)
hatToPeople[i] = new ArrayList<>();

for (int i = 0; i < nPeople; ++i)
for (final int hat : hats.get(i))