Split positions across k equally-sized desks

Question

You must deal a list of position sizes into exactly k desks so that every desk ends with the same total size. Every position goes to exactly one desk.

sizes = [4, 3, 2, 3, 5, 2, 1], k = 4
-> True     # {5}, {4,1}, {3,2}, {3,2}, each totals 5

Return whether such a k-way equal partition exists.

Accepted Answer

If the total is not divisible by k, or any single position exceeds total/k, it is impossible. Otherwise the target per desk is total/k. Backtrack by placing sizes (largest first, which prunes hard) into the k desk totals; a desk can accept the current size only if it stays within target. Two prunes make this fast: sort descending so oversized items fail early, and skip a desk whose running total duplicates one already tried at this step. For the example (total 20, target 5), the largest-first placement fills four desks of 5, so the answer is True. Time is exponential in the worst case but hea…

Split positions across k equally-sized desks

Your answer

More Coding questions