Leetcode

Number of Ways to Wear Different Hats to Each Other

May 26, 2022 by aAshish

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))
        hatToPeople[hat].add(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))
        hatToPeople[hat].add(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))
        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 & 1 << p) > 0) {
            dp[j] += dp[j ^ 1 << p];
            dp[j] %= kMod;
          }

    return dp[nAssignments - 1];
  }
}