Problem statement

https://leetcode.com/problems/number-of-ways-to-wear-different-hats-to-each-other/

Solution

Here our state is dp[mask][hat_id], where mask is bitmask for used people and hat_id is number of hats we processed so far.

Complexity

Number of states is $O(2^n \cdot m)$, where $n$ is number of people and $m$ is number of hats. So, time complexity is $O(2^n\codt n\cdot m)$, space is $O(2^n \cdot m)$.

Code

class Solution:
    def numberWays(self, hats):
        n, M, N_hats = len(hats), 10**9 + 7, 41

        hats_persons = defaultdict(set) 
        for person_id, person in enumerate(hats):
            hats_persons[person_id] = set(person)

        dp = [[0] * N_hats for _ in range(1<<n)] 
        dp[0][0] = 1

        for mask in range(0, 1<<n):
            for hat_id in range(N_hats):
                for person in range(n):
                    neib = mask ^ 1<<(person)
                    if neib != mask and hat_id in hats_persons[person]:    
                        dp[mask][hat_id] += dp[neib][hat_id-1]

                dp[mask][hat_id] = (dp[mask][hat_id] + dp[mask][hat_id-1]) % M

        return int(dp[-1][-1] % M)