4
![Stack Overflow](http://cdn.sstatic.net/stackoverflow/img/apple-touch-icon.png)
I would do this recursively
def possible_sums(arr, amt)
return [[]] if amt == 0
return [] if amt < 0
arr.reduce([]) do |sums, e|
sums.concat(
possible_sums(arr, amt-e)
.map { |sum| sum.unshift(e).sort }
)
end.uniq
end
p possible_sums([4,3,1], 10)
# => [
# ...