combination_sum_helper.call(index + 1, total, partial_combination)
        max_usage = (target - total) / candidates[index]
        (1..max_usage).each do |i|
            total += candidates[index]
            partial_combination << candidates[index]
            combination_sum_helper.call(index + 1, total, partial_combination)
        end
        max_usage.times { partial_combination.pop }

# @param {Integer[]} candidates
# @param {Integer} target
# @return {Integer[][]}
def combination_sum(candidates, target)
    combinations = []
    combination_sum_helper = lambda do |index, total, partial_combination|
        if total == target
            combinations << partial_combination.dup
            return
        end
        return unless index < candidates.size
        combination_sum_helper.call(index + 1, total, partial_combination)
        max_usage = (target - total) / candidates[index]
        (1..max_usage).each do |i|
            total += candidates[index]
            partial_combination << candidates[index]
            combination_sum_helper.call(index + 1, total, partial_combination)
        end
        max_usage.times { partial_combination.pop }
    end
    combination_sum_helper.call(0, 0, [])
    combinations
end