Number of Ways to Wear Different Hats to Each Other

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

Understanding the Visualization

Input

Each person has hat preferences

Process

Count ways to assign different hats

Output

Total number of valid assignments

Key Takeaway

🎯 Key Insight: Process hats instead of people and use bitmasks to track assignments efficiently

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

Approach	Time	Space	Notes
✓ Bottom-Up DP with Bitmask	O(40 × 2ⁿ × n)	O(2ⁿ)	Iterative DP processing hats in order with bitmask states
Memoization with Bitmask	O(40 × 2ⁿ × n)	O(40 × 2ⁿ)	Cache results using bitmask to represent assigned people
Brute Force Recursive	O(40! / (40-n)!)	O(n + 40)	Try all possible hat assignments for each person recursively

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bottom-Up DP with Bitmask — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler