##Subsets

#my first attempt
def subsets(set)
  return set if set.length == 1
  return [[set[0]], [set[1]], set] if set.length == 2
  s = subsets(set[1..-1])
  [[set[0]]] + s.map{|x| x+[set[0]]} + s
end

subsets([1,2,3]).sort_by(&:length)


# improved...

def subsets(set)
  return [set] if set.length == 1
  ss = subsets(set[1..-1])
  head = [set[0]]
  [head] + ss.map{ |set| set+head } + ss
end

p subsets([1,2,3]).sort_by(&:length)