Skip to content

1434. Number of Ways to Wear Different Hats to Each Other 👍

Approach 1: Top-down

  • Time: $O(40 \cdot 2^n \cdot n)$, where $n = |\texttt{hats}|$
  • Space: $O(40 \cdot 2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
 public:
  int numberWays(vector<vector<int>>& hats) {
    constexpr int nHats = 40;
    const int nPeople = hats.size();
    vector<vector<int>> hatToPeople(nHats + 1);
    vector<vector<int>> mem(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 numberWays(hats, 0, 1, hatToPeople, mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Returns the number of ways to assign hats 1, 2, ..., h to people, where
  // `assignment` is the bitmask of the current assignment.
  int numberWays(const vector<vector<int>>& hats, int assignment, int h,
                 const vector<vector<int>>& hatToPeople,
                 vector<vector<int>>& mem) {
    // All the people are assigned.
    if (assignment == (1 << hats.size()) - 1)
      return 1;
    if (h > 40)
      return 0;
    if (mem[h][assignment] != -1)
      return mem[h][assignment];

    // Don't wear the hat `h`.
    mem[h][assignment] = numberWays(hats, assignment, h + 1, hatToPeople, mem);

    for (const int p : hatToPeople[h]) {
      // The person `p` was assigned the hat `h` before.
      if (assignment >> p & 1)
        continue;
      // Assign the hat `h` to the person `p`.
      mem[h][assignment] +=
          numberWays(hats, assignment | 1 << p, h + 1, hatToPeople, mem);
      mem[h][assignment] %= kMod;
    }

    return mem[h][assignment];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
  public int numberWays(List<List<Integer>> hats) {
    final int nHats = 40;
    final int nPeople = hats.size();
    List<Integer>[] hatToPeople = new List[nHats + 1];
    Integer[][] mem = 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))
        hatToPeople[hat].add(i);

    return numberWays(hats, 0, 1, hatToPeople, mem);
  }

  private static final int kMod = 1_000_000_007;

  // Returns the number of ways to assign hats 1, 2, ..., h to people, where
  // `assignment` is the bitmask of the current assignment.
  private int numberWays(List<List<Integer>> hats, int assignment, int h,
                         List<Integer>[] hatToPeople, Integer[][] mem) {
    // All the people are assigned.
    if (assignment == (1 << hats.size()) - 1)
      return 1;
    if (h > 40)
      return 0;
    if (mem[h][assignment] != null)
      return mem[h][assignment];

    // Don't wear the hat `h`.
    int ans = numberWays(hats, assignment, h + 1, hatToPeople, mem);

    for (final int p : hatToPeople[h]) {
      // The person `p` was assigned the hat `h` before.
      if ((assignment >> p & 1) == 1)
        continue;
      // Assign the hat `h` to the person `p`.
      ans += numberWays(hats, assignment | 1 << p, h + 1, hatToPeople, mem);
      ans %= kMod;
    }

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

Approach 2: Bottom-up 2D DP

  • Time: $O(40 \cdot 2^n \cdot n)$
  • Space: $O(40 \cdot 2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
 public:
  int numberWays(vector<vector<int>>& hats) {
    constexpr int kMod = 1'000'000'007;
    constexpr int nHats = 40;
    const int nPeople = hats.size();
    const int nAssignments = 1 << nPeople;
    vector<vector<int>> hatToPeople(nHats + 1);
    // dp[i][j] := the number of ways to assign hats 1, 2, ..., i to people,
    // where j is the bitmask of the current assignment
    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 (int j = 0; j < nAssignments; ++j) {
        // We can cover the assignment j in 2 ways:
        // 1. Assign the first h - 1 hats to people without using the hat `h`.
        dp[h][j] += dp[h - 1][j];
        dp[h][j] %= kMod;
        for (const int p : hatToPeople[h])
          if (j >> p & 1) {
            // 2. Assign the first h - 1 hats to people without the person `p`
            //    and assign the hat `h` to the person `p`.
            dp[h][j] += dp[h - 1][j ^ 1 << p];
            dp[h][j] %= kMod;
          }
      }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
  public int numberWays(List<List<Integer>> hats) {
    final int kMod = 1_000_000_007;
    final int nHats = 40;
    final int nPeople = hats.size();
    final int nAssignments = 1 << nPeople;
    List<Integer>[] hatToPeople = new List[nHats + 1];
    // dp[i][j] := the number of ways to assign hats 1, 2, ..., i to people,
    // where j is the bitmask of the current assignment
    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))
        hatToPeople[hat].add(i);

    for (int h = 1; h <= nHats; ++h)
      for (int j = 0; j < nAssignments; ++j) {
        // We can cover the assignment j in 2 ways:
        // 1. Assign the first h - 1 hats to people without using the hat `h`.
        dp[h][j] += dp[h - 1][j];
        dp[h][j] %= kMod;
        for (final int p : hatToPeople[h])
          if ((j >> p & 1) == 1) {
            // 2. Assign the first h - 1 hats to people without the person `p`
            //    and assign the hat `h` to the 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)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  int numberWays(vector<vector<int>>& hats) {
    constexpr int kMod = 1'000'000'007;
    constexpr int nHats = 40;
    const int nPeople = hats.size();
    const int nAssignments = 1 << nPeople;
    vector<vector<int>> hatToPeople(nHats + 1);
    // dp[i] := the number of ways to assign the hats so far to people, where i
    // is the bitmask of the current assignment
    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 >> p & 1) {
            dp[j] += dp[j ^ 1 << p];
            dp[j] %= kMod;
          }

    return dp[nAssignments - 1];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public int numberWays(List<List<Integer>> hats) {
    final int kMod = 1_000_000_007;
    final int nHats = 40;
    final int nPeople = hats.size();
    final int nAssignments = 1 << nPeople;
    List<Integer>[] hatToPeople = new List[nHats + 1];
    // dp[i] := the number of ways to assign the hats so far to people, where i
    // is the bitmask of the current assignment
    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))
        hatToPeople[hat].add(i);

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

    return dp[nAssignments - 1];
  }
}