v2ex-725470-leetcode-039.rb

def combination_sum(candidates, target)
  dp = Array.new(target+1) {Array.new}
  
  candidates.each do |n|
    n.upto(target) do |t|
      next dp[t] << [n] if n == t
      dp[t] += dp[t - n].map {|comb| comb.dup + [n]}
    end
  end
  
  dp[target]
end