My submission is attached. The key insight: if you start with the
largest values you can divide the loot one gang member at a time without
fear of getting wrongly stuck. For an example of being wrongly stuck,
% ruby loot.rb 3 1 1 1 2 2 2
The shares will all have to total 3, but if you start with the light end
you might end up with (1, 1, 1) for the first guy, and then the rest of
the loot can’t be evenly split. Starting with the heavy end, though,
gets you to the right place.
Technically, this is not so much an insight as an intuition. It might
not be true in all cases. But using it as a heuristic, we can cut the
solution down to O(n^3).
The “split” function takes a list of values and the number of gang
members and returns a list of sublists that all sum to the same amount,
or nil if no solution is possible. It works by sorting the list of
values and calling “pick” once for each gang member to pick out that
member’s share from the remaining list. Using our insight, we never
backtrack in “split”. Once we’ve picked one member’s share, we never go
back to try a different combination.
“Pick” works recursively, walking from the high end of the list to the
low end, until it finds a sublist that sums to the target amount or it
runs off the end of the list. This function waits to delete elements
from the list until it finds a sublist that sums to the target amount.
In this way, “pick” doesn’t have to create any intermediate lists.