0966HardArrayDynamic ProgrammingBit ManipulationBitmaskBipartite GraphMatching (Graph)Perfect Matching

Handing Out Badges Nobody Shares

Tracked in this browser only

Trains the technique from

LeetCode 1434Number of Ways to Wear Different Hats to Each Other

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

There are some staff, and hats[i] lists the badge numbers that would suit staff member i. Every list holds distinct numbers.

Every staff member is given exactly one badge that suits them, and no two are given the same badge.

Return how many ways that can be done, modulo 10^9 + 7.

Examples

Example 1

Input: hats = [[1, 2], [1, 2]]
Output: 2

Both staff would take either badge, so one takes 1 and the other 2, or the other way round.

Example 2

Input: hats = [[1], [1]]
Output: 0

Both staff would only take badge 1, and it cannot be shared.

Example 3

Input: hats = [[1, 2, 3, 4], [2, 3], [3]]
Output: 2

Badge 3 must go to the third staff member, so badge 2 must go to the second, and the first is left with badge 1 or 4.

Constraints

1 <= hats.length <= 10
1 <= hats[i].length <= 40
1 <= hats[i][j] <= 40
The numbers in hats[i] are all different

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def number_ways(hats: list[list[int]]) -> int:

Java

public int numberWays(List<List<Integer>> hats)

The intended approach

Time O(B * 2^n * n) for B badges and n staff.Space O(2^n) for the counts.

There are at most ten staff and forty badges, so count over the badges rather than the staff: the set of staff already served fits in ten bits, while a set of badges would need forty. Turn the lists inside out first, so that each badge knows which staff it would suit. Then walk the badges one at a time, carrying for each set of served staff how many ways there are to have served exactly them using the badges so far. A badge either goes unused, leaving the counts alone, or goes to one of the staff it suits who is not yet served, which adds that staff member to the set. Walking the sets in a fresh copy each badge is what stops one badge being handed out twice. The answer is the count for the set holding every staff member, taken once all forty badges have been walked.

Pythonentry point: number_ways

def number_ways(hats):
    MOD = 1000000007
    n = len(hats)
    suits = {}
    for who in range(n):
        for badge in hats[who]:
            suits.setdefault(badge, []).append(who)
    full = (1 << n) - 1
    ways = [0] * (1 << n)
    ways[0] = 1
    for badge in sorted(suits):
        nxt = list(ways)
        for served in range(1 << n):
            if ways[served] == 0:
                continue
            for who in suits[badge]:
                if served >> who & 1:
                    continue
                mark = served | (1 << who)
                nxt[mark] = (nxt[mark] + ways[served]) % MOD
        ways = nxt
    return ways[full]

The obvious version

Serve the staff one at a time, trying every badge that suits the current one and that nobody before them has taken, and count the lines of play that serve everybody. Exponential in the staff count times the badge count, and it keeps no counts between branches.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_number_ways(hats):
    MOD = 1000000007
    n = len(hats)
    total = [0]

    def serve(who, taken):
        if who == n:
            total[0] = (total[0] + 1) % MOD
            return
        for badge in hats[who]:
            if badge in taken:
                continue
            taken.add(badge)
            serve(who + 1, taken)
            taken.remove(badge)

    serve(0, set())
    return total[0]

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in