```Here is my solution.

It first sorts the gems by value and then, tries to split them
recursively. The sorting is not necessary for split_loot to work, but it
works much faster on sorted sets.

If only a number of adventurers and no loot is given, then a random loot
is generated.

Dominik

def split_loot(cnt, gems, first_call = true)
return [gems] if cnt == 1
sum = gems.inject(0) { |s, n| s + n }
share = sum / cnt
if first_call
# only do these checks once
if sum % share != 0 || gems.max > share || gems.empty?
raise "impossible"
end
end
# search all subsets of the gems whose sum is share, for each try to
# split the remaining loot into cnt - 1 parts
choose_stack = [0]
share_sum = gems.first
last = gems.size - 1
until choose_stack.empty?
while share_sum < share && choose_stack.last < last
choose_stack << choose_stack.last + 1
share_sum += gems[choose_stack.last]
end
if share_sum == share
# recursive call
rest_gems = gems.values_at(*((0...gems.size).to_a - choose_stack))
if (res = split_loot(cnt - 1, rest_gems, false) rescue nil)
return (res << gems.values_at(*choose_stack))
end
end
if choose_stack.last == last
share_sum -= gems[last]
choose_stack.pop
end
unless choose_stack.empty?
share_sum -= gems[choose_stack.last]
choose_stack << choose_stack.pop + 1
share_sum += gems[choose_stack.last]
end
end
raise "impossible"
end

if \$0 == __FILE__
begin
if ARGV.size >= 2
cnt, *gems = ARGV.map { |s| Integer(s) }
else
# generate a test
cnt = ARGV.shift.to_i
share_sum = rand(1000)
gems = []
cnt.times {
rest = share_sum
while rest > 0
cur = rand(rest) + 1
gems << cur
rest -= cur
end
}
end
split_loot(cnt, gems.sort.reverse).each_with_index { |s, i|
puts "#{i+1}: #{s.join(' ')}"
}
rescue => e
puts e
end
end

```