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