Share the numbers equally
Decide whether numbers can be split into k groups with the same sum, by filling the groups one number at a time and pruning groups that would be tried twice or overflow. About 26 minutes.
A target per group
If numbers can be split into k groups with equal sums, each group must sum to the total divided by k. If that division is not exact, or the biggest number exceeds that target, the answer is no at once.
Otherwise, keep a running sum for each of the k groups, and place the numbers one by one, trying each group. A placement is only allowed if the group's sum does not go above the target.
share = sum(items) // people leftover = sum(items) % people
5 fills the first group on its own (sum 5).
Prune the repeats
Sort the numbers from big to small and place the big ones first, as they fail fastest. Two groups with the same current sum are interchangeable, so for one number try only one of them. Remember the sums already tried for this number in a small set.
If all the numbers are placed, every group is full, since the total matches the sum of the targets. The search then returns yes. If every choice for some number fails, undo and return no.
if sums[g] in seen:
continue # a group tried alreadyWhy try only one of several groups that have the same current sum?
- AThey are interchangeable, so the outcome is the same whichever is chosen
- BThe first one is always the best
- CThe rules require it
Show the answer
They are interchangeable, so the outcome is the same whichever is chosen. Trying more than one only repeats work.
Partition to k equal sum subsets
You get a list nums of positive whole numbers and a number k. Return true if the numbers can be split into k non-empty groups, every number going to exactly one group, so that all the groups have the same sum. Otherwise return false.
nums = [4, 3, 2, 3, 5, 2, 1], k = 4 → true
1 ≤ k ≤ length of nums ≤ 16 · 1 ≤ nums[i] ≤ 10,000