#!/usr/bin/env ruby

class SubsetSum
  attr_accessor :nearest

  def initialize(items, target)
    @nearest = 0
    for combination_dec in 1..(2**items.size - 1)
      subset_sum = 0
      combination_bin = combination_dec.to_s(base=2).rjust(items.size, "0")
      for digit in 0..items.size - 1
        subset_sum += items[digit] if combination_bin[digit, 1].eql? "1"
      end
      @nearest = subset_sum if (target - subset_sum) < (target - nearest)
    end
  end
end

subset_sum = SubsetSum.new(
  [ 309, 122, 212, 151, 245, 107, 180, 174, 142, 244, 439, 278, 106, 286, 183, 136, 184, 188, 123 ],
  2165
)

puts subset_sum.nearest