class SetPartitioner

  def initialize(min, max, total)
    @min = min
    @max = max
    @total = total
  end

  def any?
    sets.present?
  end

  def sets
    @sets ||= get_sets
  end

  def optimal_set
    sets.min_by { |s| s.length }.reverse
  end

  private

    def get_sets
      Timeout::timeout(3) do
        max_group_size = (@total / @min.to_f).ceil
        range = (@min..@max).to_a
        all_options = ([range] * max_group_size).flatten.sort.reverse
        sets = subsets_with_sum(all_options)
        sets = sets.map { |r| r.sort }.uniq
        sets.sort
      end
    rescue Timeout::Error
      raise "Timeout in SetPartitioner: #{@min}-#{@max} into #{@total}."
    end

    def subsets_with_sum(numbers, partial=[])
      result = []
      sum = partial.inject(0, :+)
      if sum == @total
        result << partial
      elsif sum < @total
        (0..(numbers.length - 1)).each do |i|
          n = numbers[i]
          remaining = numbers.drop(i + 1)
          result += subsets_with_sum(remaining, partial + [n])
          break unless result.blank? # return only the first
        end
      end
      result
    end

end