Optimizing sum_combination_for(n) code

I'm working on a piece of code for calculating all the possible combinations of numbers that sum to n. For example:

sum_combination(3) = [
  [1,1,1],
  [1,2],
  [3]
]

So my ruby code is this:

class Integer
  SUM_COMBINATION = {
    1 => [[1]],
    2 => [[1,1],[2]],
    3 => [[1,1,1],[1,2],[3]]
  }

  def sum_combination
    SUM_COMBINATION[self] ||= (
      (self-1).downto((self/2.0).ceil).map do |n|
        n.sum_combination.map { |c| (c+[self-n]).sort }
      end.flatten(1).uniq + [[self]]
    )
  end
end

The code works, but it's insanely slow for numbers above 50.

Notes:

• Using uniq in a combinatorics problem is most likely a code smell. It means that you are generating more elements that you need (waste of space and time) and later you have to remove them (waste of more time).

• The natural way seems to be passing down which is the maximum subtraction value allowed, that way you won't repeat values in different orders.

• I wouldn't extend Integer for a method like this, it does not seem a general enough abstraction.

• Note that map + flatten(1) -> flat_map.

I'd write (also in functional style, as your code):

module Combinatorics
  def self.sets_with_sum(value, max = value)
    if value == 0
      [[]]
    else
      1.upto(max).flat_map do |n|
        sets_with_sum(value - n, [value, n].min).map do |ns|
          [n] + ns
        end
      end
    end 
  end
end

p Combinatorics.sets_with_sum(4)
p Combinatorics.sets_with_sum(50).size

Even though I don't memoize anything, the performance is acceptable:

$ time ruby sum-combination.rb
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
204226

real    0m8.416s

StackExchange Code Review Q#25148, answer score: 5