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]]    )  endendThe code works, but it's insanely slow for numbers above 50, meaning I never had enough patience to watch it finish :(...
Optimizing sum_combination_for(n) code
ruby
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).Taking paper and pencil and drawing some trees, 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. This method has been around since Ruby 1.9.2 but for some reason it's still pretty much ignored.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   endendp Combinatorics.sets_with_sum(4)p Combinatorics.sets_with_sum(50).sizeNote that I don't memoize anything yet the performance seems acceptable:$ time ruby sum-combination.rb[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]204226real    0m8.416s