def subsets(array)
  subsets = []
  array.each do |elem|
    new = subsets.inject([]) { |accum, n| accum << n.dup.push(elem) }
    subsets.concat(new)
    subsets << [elem]
  end
  subsets
end

def filter_subsets(subsets, array)
  lookup = array.inject({}) { |hash, elem| hash[elem] = true && hash }
  subsets.inject([]) do |accum, subset|
    if (subset.length > 1) && lookup[subset.inject(:+)]
      accum << subset
    end
    accum
  end
end

array = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99]
sets = subsets(array)

puts "generated #{sets.length} subsets"

puts "filtering subsets"
fsets = filter_subsets(sets, array)
puts "#{fsets.length} matching subsets"


# $ time ruby find_subsets.rb
# => Generated 4194303 subsets
# filtering subsets
# 179 matching subsets
# 42.422 secs