Commit 90b7a3f

@@ -162,12 +162,13 @@ describe "sum_subsets" do
   def sum_subsets(numbers, target, partial=[], results = {})
     sum = partial.inject(0, :+)
     results[partial] = true if sum == target
-    return results.keys if sum >= target
+    return nil if sum > target
 
     numbers.size.times do |n|
       item = numbers[n]
       remaining = numbers[(n + 1)..-1]
-      sum_subsets(remaining, target, partial + [item], results)
+      break if results.key?(remaining)
+      break if sum_subsets(remaining, target, partial + [item], results).nil?
     end
     results.keys
   end
@@ -179,11 +180,10 @@ describe "sum_subsets" do
     { arr: [1, 1, 1, 1, 1, 1, 1, 1, 1], num: 9, expected: [[1,1,1,1,1,1,1,1,1]] },
     { arr: [1, 1, 2, 2, 2, 5, 5, 6, 8, 8], num: 9, expected: [[1,1,2,5], [1,2,6], [1,8], [2,2,5]] },
     { arr: [1, 1, 2, 4, 4, 4, 7, 9, 9, 13, 13, 13, 15, 15, 16, 16, 16, 19, 19, 20], num: 36, expected: [[1,1,2,4,4,4,7,13], [1,1,2,4,4,4,20], [1,1,2,4,4,9,15], [1,1,2,4,9,19], [1,1,2,4,13,15], [1,1,2,7,9,16], [1,1,2,13,19], [1,1,2,16,16], [1,1,4,4,4,7,15], [1,1,4,4,4,9,13], [1,1,4,4,7,19], [1,1,4,4,13,13], [1,1,4,15,15], [1,1,9,9,16], [1,1,15,19], [1,2,4,4,7,9,9], [1,2,4,4,9,16], [1,2,4,7,9,13], [1,2,4,9,20], [1,2,4,13,16], [1,2,7,13,13], [1,2,9,9,15], [1,2,13,20], [1,4,4,4,7,16], [1,4,4,7,20], [1,4,7,9,15], [1,4,9,9,13], [1,4,15,16], [1,7,9,19], [1,7,13,15], [1,9,13,13], [1,15,20], [1,16,19], [2,4,4,4,7,15], [2,4,4,4,9,13], [2,4,4,7,19], [2,4,4,13,13], [2,4,15,15], [2,9,9,16], [2,15,19], [4,4,4,9,15], [4,4,9,19], [4,4,13,15], [4,7,9,16], [4,13,19], [4,16,16], [7,9,20], [7,13,16], [16,20]] },
+    { arr: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], num: 10, expected: [[1, 2, 3, 4], [1, 2, 7], [1, 3, 6], [1, 4, 5], [1, 9], [2, 3, 5], [2, 8], [3, 7], [4, 6], [10]] },
   ].each do |x|
     it do
-      result = with_profiler do
-        sum_subsets(x[:arr], x[:num])
-      end
+      result = sum_subsets(x[:arr], x[:num])
       expect(result).to eql(x[:expected])
     end
   end