def find_subsets(arr)
  subset = arr.slice(0..-2)
  tail = arr[-1]
  new_sets = []
  new_sets.push [tail]

  if subset.size >= 2
    sets = find_subsets(subset)
    sets.each do |s|
      new_sets.push( [s, tail].flatten )
    end
    new_sets = new_sets.concat sets
  else
    new_sets.push subset
    new_sets.push [subset, tail].flatten
  end

  return new_sets

end

def subset_sum(arr, sum)
  find_subsets(arr).select {|subset| subset.inject{|a,b| a+b} == sum }
end