Solves the problem that is the basis of the example Google Interview here: https://www.youtube.com/watch?v=XKu_SEDAykw

google_interview.rb

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

def summables(vector, remainder, so_far)
  return Set.new if remainder < 0                     #did not find a sum
  return [so_far].to_set if remainder == 0            #found a sum

  car = vector[0]
  return Set.new if car == nil                        #did not find a sum

  cdr = vector[1..-1]                                 #keep looking

  answers =
    if car > 0
      summables(cdr, remainder - car, so_far + [car]) #summables including positive car
    else
      Set.new  
    end
      .merge summables(cdr, remainder, so_far)        #merged with summables excluding car
  return answers
end

def find_summables(vector, sum)
  summables(vector, sum, []).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")