Fill one group at a time
Track which items are used, and how full the current group is, in a single list indexed by the set. About 16 minutes.
Fair shares for everyone
You have a list of numbers and want to split them into k groups, every group with the same total. Think of sharing out chores so that each of k people gets the same number of minutes of work, and no chore can be cut in two.
Two quick checks come first. The total must divide evenly by k, and no single number can be bigger than the share each group gets. After that, it comes down to choosing which numbers go together.
Fill a group, then start the next
Add the numbers one at a time into a current group. If an item fits, add it. If adding it would overflow the share, that move is not allowed. When a group is exactly full, the next item starts a fresh group.
The fill level of the current group is just the total of all used items, with whole shares taken off. So one entry per set of used items is enough: how full is the current group, or that the set cannot be reached at all. The answer is whether the set of all items ends at a fill level of zero.
total = sum(nums)
if total % k:
return False- fill
- 0
- used
- none
Start with nothing used. The current group is empty: fill 0.
The current group holds 3 out of a share of 4. Can you add an item of size 2?
- ANo
- BYes, and the extra 1 goes to the next group
- CYes, groups can go over
Show the answer
No. 3 + 2 = 5 would overflow the share, and items can't be cut in two.
Split into equal groups
You get a list nums of positive whole numbers and a number k. Return true if the numbers can be split into k groups, every number going to exactly one group, so that all k groups have the same total. Otherwise return false.
nums = [4, 3, 2, 3, 5, 2, 1], k = 4 → true
1 ≤ length ≤ 16 · 1 ≤ k ≤ 16 · 1 ≤ nums[i] ≤ 1,000