#
# Google interview question: find all combinations that sum up to a value
#
require 'set'

def summables(vector, remainder, so_far, answers)
  answers.add(so_far) if remainder == 0

  car = vector[0]
  return answers if car == nil

  cdr = vector[1..-1]

  summables(cdr, remainder - car, so_far + [car], answers) if car <= remainder  && car > 0 #summables including car where no soln yet
  summables(cdr, remainder, so_far, answers) #all summables excluding car
end

def find_summables(vector, sum)
  summables(vector, sum, [], Set.new).to_a
end


print(find_summables([1, 2, 3, 5, 7, 2], 7))
print("\n----\n")

print(find_summables([1,4,3,3,6,8,8,8,8,8,8,8,8,7,5,5,45,6,7,8,8,7,7,1,6,5,2], 13))
print("\n----\n")