A chemistry teacher splits her n students (an even number) into lab pairs; every student is in exactly one pair. From past projects she has a table score[i][j]: how well students i and j work together. It is symmetric (score[i][j] == score[j][i]) and score[i][i] == 0.
Implement best_pairing(score: list[list[int]]) -> int: the largest possible sum of the scores of the chosen pairs.
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
With no students (n = 0) the answer is 0.
Constraints: n is even, 0 <= n <= 18, 0 <= score[i][j] <= 100. Listing every pairing is too slow at n = 18 (over 34 million of them); a table over subsets has 2^18 = 262144 entries.
Show hint
let best[mask] be the top score for pairing up exactly the students in mask. To avoid counting the same pairing many times, always pair the lowest-numbered student not yet in mask, call them i, with some other free student j: that leads to best[mask | 1 << i | 1 << j]. The answer is best[(1 << n) - 1].