Number of Ways to Wear Different Hats to Each Other - Problem

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 i-th 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 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: hats = [[3,4],[4,5],[5]]

› Output: 1

💡 Note: Only one way: person 0 wears hat 3, person 1 wears hat 4, person 2 wears hat 5

Example 2 — Multiple Options

$ Input: hats = [[3,5,1],[3,5]]

› Output: 4

💡 Note: Four ways: (1,3), (1,5), (3,5), (5,3) where (x,y) means person 0 wears hat x, person 1 wears hat y

Example 3 — Single Person

$ Input: hats = [[1,2,3,4,5,6,7,8,9,10]]

› Output: 10

💡 Note: One person can choose any of the 10 hats they like

Constraints

n == hats.length
1 ≤ n ≤ 10
1 ≤ hats[i].length ≤ 40
1 ≤ hats[i][j] ≤ 40
All values in hats[i] are unique

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 f Facebook 8

This problem requires dynamic programming with bitmasks to efficiently count hat assignments. The key insight is to process hats one by one and use bitmasks to represent which people have been assigned hats. The optimal approach uses bottom-up DP with Time: O(40 × 2ⁿ × n), Space: O(2ⁿ).

Common Approaches

✓ Bottom-Up DP with Bitmask

⏱️ Time: O(40 × 2ⁿ × n) Space: O(2ⁿ)

Build the solution bottom-up by processing each hat and maintaining DP states for all possible people assignments using bitmasks. This avoids recursion overhead.

Brute Force Recursive

⏱️ Time: O(40! / (40-n)!) Space: O(n + 40)

For each person, try assigning each of their preferred hats and recursively solve for remaining people. Use backtracking to ensure no two people wear the same hat.

Memoization with Bitmask

⏱️ Time: O(40 × 2ⁿ × n) Space: O(40 × 2ⁿ)

Use dynamic programming with memoization where state is represented by a bitmask indicating which people have been assigned hats. Process hats one by one and decide which person gets each hat.

Bottom-Up DP with Bitmask — Algorithm Steps

Create mapping from hats to people who like them
Initialize DP array where dp[mask] = ways to assign hats to people in mask
For each hat, update DP by trying to assign it to each person who likes it
Return dp[(1<<n)-1] representing all people have hats

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

dp[0] = 1 (no one has hats)

Process Hat 1

Update DP for assignments

Final State

dp[111] = ways for all people

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MOD 1000000007
#define MAX_HATS 41
#define MAX_PEOPLE 10

int hatToPeople[MAX_HATS][MAX_PEOPLE];
int hatToPeopleSize[MAX_HATS];

int solution(int** hats, int* hatSizes, int n) {
    // Initialize
    for (int i = 0; i < MAX_HATS; i++) {
        hatToPeopleSize[i] = 0;
    }
    
    // Build hat to people mapping
    for (int person = 0; person < n; person++) {
        for (int i = 0; i < hatSizes[person]; i++) {
            int hat = hats[person][i];
            hatToPeople[hat][hatToPeopleSize[hat]++] = person;
        }
    }
    
    // DP array
    long long* dp = calloc(1 << n, sizeof(long long));
    dp[0] = 1;
    
    // Process each hat
    for (int hat = 1; hat < MAX_HATS; hat++) {
        if (hatToPeopleSize[hat] == 0) continue;
        
        // Process in reverse order
        for (int mask = (1 << n) - 1; mask >= 0; mask--) {
            if (dp[mask] == 0) continue;
            
            // Try assigning this hat
            for (int i = 0; i < hatToPeopleSize[hat]; i++) {
                int person = hatToPeople[hat][i];
                if (!(mask & (1 << person))) {
                    int newMask = mask | (1 << person);
                    dp[newMask] = (dp[newMask] + dp[mask]) % MOD;
                }
            }
        }
    }
    
    int result = dp[(1 << n) - 1];
    free(dp);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int** hats = malloc(10 * sizeof(int*));
    int* hatSizes = malloc(10 * sizeof(int));
    int n = 0;
    
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            hats[n] = malloc(40 * sizeof(int));
            hatSizes[n] = 0;
            
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9') {
                    int num = 0;
                    while (*ptr >= '0' && *ptr <= '9') {
                        num = num * 10 + (*ptr - '0');
                        ptr++;
                    }
                    hats[n][hatSizes[n]++] = num;
                } else {
                    ptr++;
                }
            }
            n++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(hats, hatSizes, n));
    
    for (int i = 0; i < n; i++) free(hats[i]);
    free(hats);
    free(hatSizes);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(40 × 2ⁿ × n)

40 hats × 2^n possible people masks × n people to try per hat

✓ Linear Growth

Space Complexity

O(2ⁿ)

DP array stores ways for each possible people assignment mask

✓ Linear Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Number of Ways to Wear Different Hats to Each Other - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bottom-Up DP with Bitmask — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler