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

ZGVmIGNoYW5nZSh0YXJnZXQsIHNpZ24sIGNvaW5zLCBuKQogICgxLi5jb2lucy5zaXplKS5lYWNoIGRvIHxrfAogICAgY29pbnMuY29tYmluYXRpb24oaykuZWFjaCBkbyB8cG9zc3wKICAgICAgbmV4dCB1bmxlc3MgZXZhbCgiI3trfSAje3NpZ259ICN7bn0iKQogICAgICByZXR1cm4gcG9zcyBpZiBwb3NzLnJlZHVjZSg6KykgPT0gdGFyZ2V0CiAgICBlbmQKICBlbmQKICAnTm8gc29sdXRpb24gcG9zc2libGUnCmVuZAoKaWYgX19GSUxFX18gPT0gJDAKICBwIGNoYW5nZSgxNTAsICc8JywgWzEwMCwgNTAsIDUwLCA1MCwgNTBdLCA1KQogIHAgY2hhbmdlKDEzMCwgJzwnLCBbMTAwLCAyMCwgMTgsIDEyLCA1LCA1XSwgNikKICBwIGNoYW5nZSgyMDAsICc+PScsIFs1MCwgNTAsIDIwLCAyMCwgMTBdLCA1KQogIHAgY2hhbmdlKDE1MCwgJzw9JywgWzEwMCwgNTAsIDUwLCA1MCwgNTBdLCAyKQogIHAgY2hhbmdlKDEzMCwgJzw9JywgWzEwMCwgMjAsIDE4LCAxMiwgNSwgNV0sIDMpCiAgI3BwIGNoYW5nZSgxNTAsICc8PScsIEFycmF5Lm5ldygxMDAwMCwgMSksIDE1MCkKZW5k