def change(target, sign, coins, n)
  (1..coins.size).each do |k|
    coins.combination(k).each do |poss|
      next unless eval("#{k} #{sign} #{n}")
      return poss if poss.reduce(:+) == target
    end
  end
  'No solution possible'
end

if __FILE__ == $0
  p change(150, '<', [100, 50, 50, 50, 50], 5)
  p change(130, '<', [100, 20, 18, 12, 5, 5], 6)
  p change(200, '>=', [50, 50, 20, 20, 10], 5)
  p change(150, '<=', [100, 50, 50, 50, 50], 2)
  p change(130, '<=', [100, 20, 18, 12, 5, 5], 3)
  #pp change(150, '<=', Array.new(10000, 1), 150)
end