def combination_sum(candidates, target)
  tmp, res = [], []
  sub_sum(candidates.sort!, tmp, target, res)
  res
end

def sub_sum(candidates, tmp, target, res)
  return if target < 0
  res << tmp.dup if target == 0

  candidates.each_with_index do |c, i|
    sub_sum(candidates[i..-1], tmp << c, target - c, res)
    tmp.pop
  end
end