Number of ways to wear different hats to each other

Array Dynamic Programming Bit Manipulation Bitmask

45.7% acceptance

Feb 25, 2026

959

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 n people can wear different hats from each other. Since the answer may be too large, return it modulo 109 + 7.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn number_ways(hats: Vec<Vec<i32>>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = hats.len();
    let full_mask = (1usize << n) - 1;
    let mut hat_to_people: Vec<Vec<usize>> = vec![vec![]; 41];
    for (i, person_hats) in hats.iter().enumerate() {
      for &h in person_hats {
        hat_to_people[h as usize].push(i);
      }
    }
    let mut dp = vec![0i64; 1 << n];
    dp[0] = 1;
    for h in 1..=40 {
      let mut new_dp = dp.clone();
      for &p in &hat_to_people[h] {
        for mask in 0..=full_mask {
          if mask & (1 << p) != 0 {
            new_dp[mask] = (new_dp[mask] + dp[mask ^ (1 << p)]) % MOD;
          }
        }
      }
      dp = new_dp;
    }
    dp[full_mask] as i32
  }
}