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

Description

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

Given a 2D integer array hats, where hats[i] is a list of all hats preferred by the ith 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 109 + 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.

 

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.

 

Solutions

Solution: Dynamic Programming + Bit Manipulation

• Time complexity: O(40*2ⁿ)
• Space complexity: O(40*2ⁿ)

 

JavaScript

/**
 * @param {number[][]} hats
 * @return {number}
 */
const numberWays = function (hats) {
  const MODULO = 10 ** 9 + 7;
  const HAT_TYPES = 40;
  const n = hats.length;
  const hatsWithWearPersons = Array.from({ length: HAT_TYPES + 1 }, () => []);
  const dp = Array.from({ length: HAT_TYPES + 1 }, () => new Array(1 << n).fill(-1));

  for (let person = 0; person < n; person++) {
    const wearHats = hats[person];

    for (const hat of wearHats) {
      hatsWithWearPersons[hat].push(person);
    }
  }

  const wearHat = (hat, mask) => {
    if (mask === (1 << n) - 1) return 1;
    if (hat > HAT_TYPES) return 0;
    if (dp[hat][mask] !== -1) return dp[hat][mask];
    let result = wearHat(hat + 1, mask);

    for (const person of hatsWithWearPersons[hat]) {
      const personMask = 1 << person;

      if (mask & personMask) continue;

      result = (result + wearHat(hat + 1, mask | personMask)) % MODULO;
    }

    dp[hat][mask] = result;

    return result;
  };

  return wearHat(1, 0);
};