There are n workers and n jobs. cost[i][j] is what worker i charges for job j. Every worker must get exactly one job and every job exactly one worker.
Implement min_assignment(cost: list[list[int]]) -> int: the smallest possible total.
min_assignment([[9, 2],
[3, 8]]) # 5 worker 0 -> job 1 (2), worker 1 -> job 0 (3)
min_assignment([[4, 1, 3],
[2, 0, 5],
[3, 2, 2]]) # 5 0 -> job 1, 1 -> job 0, 2 -> job 2: 1 + 2 + 2
With n = 0 the answer is 0.
Constraints: 0 <= n <= 14, 0 <= cost[i][j] <= 1000. Trying all n! orders is far too slow at n = 14 (87 billion); a table over subsets of jobs has only 2^14 = 16384 entries.
Show hint
let best[mask] be the cheapest way to hand out exactly the jobs whose bits are set in mask to workers 0 .. popcount(mask) - 1; the next worker is i = popcount(mask), and giving them a free job j leads to best[mask | 1 << j].