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 =&gt; [[1]],
    2 =&gt; [[1,1],[2]],
    3 =&gt; [[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