Find combinations of sets built from a range that add to a given value

set_partitioner.rb

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

set_partitioner_test.rb

require 'test_helper'

class SetPartitionerTest < ActiveSupport::TestCase

  test "normal" do
    sp = SetPartitioner.new(3, 5, 12)
    # assert_equal [[3, 3, 3, 3], [3, 4, 5], [4, 4, 4]], sp.sets
    assert_equal [5, 4, 3], sp.optimal_set
    assert sp.any?
  end

  test "empty" do
    sp = SetPartitioner.new(12, 15, 35)
    refute sp.any?
  end

  test "big set" do
    sp = SetPartitioner.new(5, 9, 66)
    assert_equal [9, 9, 9, 9, 9, 9, 7, 5], sp.optimal_set
  end

end

With a little help from here: http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum

Remove break unless result.blank? on line 46 to return all sets. Left in as only optimal_set required and speeds it up a lot.