Number of Ways to Wear Different Hats to Each Other solution and explanation

MOD = 10**9 + 7

def number_ways(hats):
    n = len(hats)
    all_mask = (1 << n) - 1
    dp = {}
    hat_to_people = [[] for _ in range(41)]
    for person, hat_list in enumerate(hats):
        for hat in hat_list:
            hat_to_people[hat].append(person)
    
    def ways(hat, mask):
        if mask == all_mask:
            return 1
        if hat > 40:
            return 0
        if (hat, mask) in dp:
            return dp[(hat, mask)]
        ans = ways(hat + 1, mask)
        for person in hat_to_people[hat]:
            if mask & (1 << person) == 0:
                ans += ways(hat + 1, mask | (1 << person))
                ans %= MOD
        dp[(hat, mask)] = ans
        return ans
    
    return ways(1,0)

const MOD = 10**9 + 7;

function numberOfWays(hats) {
    const n = hats.length;
    const allMask = (1 << n) - 1;
    const dp = new Map();
    const hatToPeople = Array.from({ length: 41 }, () => []);

    hats.forEach((hatList, person) => {
        hatList.forEach(hat => {
            hatToPeople[hat].push(person);
        });
    });

    function ways(hat, mask) {
        if (mask === allMask) return 1;
        if (hat > 40) return 0;
        const key = `${hat},${mask}`;
        if (dp.has(key)) return dp.get(key);
        let ans = ways(hat + 1, mask);
        hatToPeople[hat].forEach(person => {
            if ((mask & (1 << person)) === 0) {
                ans += ways(hat + 1, mask | (1 << person));
                ans %= MOD;
            }
        });
        dp.set(key, ans);
        return ans;
    }

    return ways(1, 0);
}

import java.util.*;

class Solution {
    private static final int MOD = 1000000007;
    
    public int numberOfWays(List<List<Integer>> hats) {
        int n = hats.size();
        List<Integer>[] peopleWithHat = new ArrayList[41];
        for (int i = 0; i <= 40; i++) {
            peopleWithHat[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            for (int hat : hats.get(i)) {
                peopleWithHat[hat].add(i);
            }
        }
        Map<Integer, Integer> dp = new HashMap<>();
        return dfs(0, 0, peopleWithHat, dp, n);
    }
    
    private int dfs(int hat, int mask, List<Integer>[] peopleWithHat, Map<Integer, Integer> dp, int n) {
        if (mask == (1 << n) - 1) return 1;
        if (hat > 40) return 0;
        int key = (hat << 10) | mask;
        if (dp.containsKey(key)) return dp.get(key);
        int ans = dfs(hat + 1, mask, peopleWithHat, dp, n);
        for (int person : peopleWithHat[hat]) {
            if ((mask & (1 << person)) == 0) {
                ans = (ans + dfs(hat + 1, mask | (1 << person), peopleWithHat, dp, n)) % MOD;
            }
        }
        dp.put(key, ans);
        return ans;
    }
}

#include <vector>
#include <unordered_map>

using namespace std;
#define MOD 1000000007

int numberOfWays(vector<vector<int>>& hats) {
    int n = hats.size();
    vector<vector<int>> people_with_hat(41);
    for (int i = 0; i < n; ++i) {
        for (int hat : hats[i]) {
            people_with_hat[hat].push_back(i);
        }
    }
    unordered_map<int, int> dp;
    return dfs(0, 0, people_with_hat, dp, n);
}

int dfs(int hat, int mask, vector<vector<int>>& people_with_hat, unordered_map<int, int>& dp, int n) {
    if (mask == (1 << n) - 1) return 1;
    if (hat > 40) return 0;
    if (dp.count((hat << 10) | mask)) return dp[(hat << 10) | mask];
    int ans = dfs(hat + 1, mask, people_with_hat, dp, n);
    for (int person : people_with_hat[hat]) {
        if (!(mask & (1 << person))) {
            ans = (ans + dfs(hat + 1, mask | (1 << person), people_with_hat, dp, n)) % MOD;
        }
    }
    dp[(hat << 10) | mask] = ans;
    return ans;
}

function numberWays(hats: number[][]): number {
    const n = hats.length;
    const m = Math.max(...hats.flat());
    const g: number[][] = Array.from({ length: m + 1 }, () => []);
    for (let i = 0; i < n; ++i) {
        for (const v of hats[i]) {
            g[v].push(i);
        }
    }
    const f: number[][] = Array.from({ length: m + 1 }, () =>
        Array.from({ length: 1 << n }, () => 0),
    );
    f[0][0] = 1;
    const mod = 1e9 + 7;
    for (let i = 1; i <= m; ++i) {
        for (let j = 0; j < 1 << n; ++j) {
            f[i][j] = f[i - 1][j];
            for (const k of g[i]) {
                if (((j >> k) & 1) === 1) {
                    f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod;
                }
            }
        }
    }
    return f[m][(1 << n) - 1];
}

func numberWays(hats [][]int) int {
	n := len(hats)
	m := 0
	for _, h := range hats {
		m = max(m, slices.Max(h))
	}
	g := make([][]int, m+1)
	for i, h := range hats {
		for _, v := range h {
			g[v] = append(g[v], i)
		}
	}
	const mod = 1e9 + 7
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, 1<<n)
	}
	f[0][0] = 1
	for i := 1; i <= m; i++ {
		for j := 0; j < 1<<n; j++ {
			f[i][j] = f[i-1][j]
			for _, k := range g[i] {
				if j>>k&1 == 1 {
					f[i][j] = (f[i][j] + f[i-1][j^(1<<k)]) % mod
				}
			}
		}
	}
	return f[m][(1<<n)-1]
}