[Algorithm] 46 week(12.12 ~ 12.17) 3/3

39. Combination Sum

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    let result = [];

    const dfs = (sum, index, path) => {
        if(sum < 0) return;

        if(sum === 0){
            result.push(path);
            return;
        }

        for(let i = index; i < candidates.length; i++){
            dfs(sum - candidates[i], i, [...path, candidates[i]])
        }
    }

    dfs(target, 0, [])

    return result;
};