A chemistry teacher splits her n students (n even) into lab pairs. score[i][j] says how well i and j work together (symmetric, score[i][i] == 0).
Implement best_pairing(score: list[list[int]]) -> int: the largest total score of a pairing (0 when n = 0).
best_pairing([[0, 9, 8, 0],
[9, 0, 0, 8],
[8, 0, 0, 1],
[0, 8, 1, 0]]) # 16 pairs (0, 2) and (1, 3): 8 + 8
# grabbing the best pair (0, 1) first leaves (2, 3): only 9 + 1
0 <= n <= 18, scores 0..100.
⭐ Bonus: listing every pairing passes for small n; a speed test with 18 students (over 34 million pairings) earns a star with a table over subsets (2^18 entries).
Show hint
best[mask] is the top score for pairing the students in mask. To avoid repeats, always pair the lowest free student i with some free j, leading to best[mask | 1 << i | 1 << j].