Count Distinct Hat Assignments and Maximize Hat Points

Each person lists the hats they are willing to wear. Assign one acceptable hat to every person, using each hat at most once. Every hat also has a point value. Return both the total number of valid assignments and the maximum total points among valid assignments.

Implement hat_assignments(preferences: int[][], points: int[]) -> int[], returning [number_of_assignments, maximum_points].

Constraints & Assumptions

• Hat IDs are 1 through H, where H == len(points) and points[h-1] is hat h's point value.
• 1 <= H <= 12; there are 0 through 8 people. These small practice bounds allow an exact count without a modulus and keep results within signed 32-bit integers.
• Each preference list contains distinct valid hat IDs and may be empty.
• Hat points are nonnegative integers at most 1,000,000. An assignment's score is the sum of points of its assigned hats, counted once per used hat.
• People are distinct, so exchanging two acceptable hats between people creates a different assignment even if the total points stay equal.
• If no complete assignment exists, return [0, -1]. With no people, the one empty assignment has score zero, so return [1, 0].
• Do not count partial assignments or require every available hat to be used.

Examples

preferences = [[1,2],[2,3]]
points = [5,2,9]
result = [3,14]

The assignments are (1,2), (1,3), and (2,3). Their scores are 7, 14, and 11.

preferences = [[1],[1]]
points = [8]
result = [0,-1]

Explain how the counting state and maximum-score state are combined without counting an assignment twice. Compare bounded backtracking with a bitmask dynamic program under the stated small sizes.

Hint: Separate ways from best score

Two partial assignments may reach the same availability state. Their counts should be added, while their best achievable scores require a maximum rather than addition.

Count Acceptable Hat Assignments and Maximize Points

Approach

Process distinct people in their given order. A mask marks hats already used by the processed prefix. ways[mask] counts its assignments, while best[mask] stores the maximum score or -1 when unreachable. For each acceptable unused hat of the next person, transition to mask plus that bit: add the old count and maximize old best plus the hat value. Every complete assignment has one unique sequence of person-by-person choices, so it contributes exactly once. Paths merging into the same mask require count addition, not deduplication; score aggregation uses maximum. Although a fixed used-hat mask here already determines its point sum, maintaining the parallel best state makes the two aggregation rules explicit. Use fresh arrays per person to prevent assigning one person multiple times in a layer. After all people, sum counts across all reachable masks and maximize scores; do not require all hats to be used. With no people, the initial empty state returns [1,0]; unreachable final layers return [0,-1]. Bounded backtracking also works but may enumerate up to 12-permute-8 complete assignments. The bitmask dynamic program merges shared states, taking O(PH2^H) time and O(2^H) space for P people and H hats. The stated count and score bounds fit signed 32-bit results.

• Time complexity: O(P * H * 2^H)
• Space complexity: O(2^H)