LeetCode #39 Combination Sum

https://leetcode.com/problems/combination-sum/

문제 파악

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
주어진 중복 없는 숫자 배열을 가지고 합이 목표 숫자가 되는 배열 조합을 구하라.
The same number may be chosen from candidates an unlimited number of times.
숫자는 중복이 있을 수 있다.
Two combinations are unique if the frequency of at least one of the chosen numbers is different.
결과 조합은 중복되지 않는다.

예제 파악

코드

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
    candidates.sort((a, b) => a - b); // 오름차순 
    
    let answer = [];

    dfs([], 0, 0);

    /**
     * 
     * @param {number[]} path 현재 조합 
     * @param {number} sum 현재 합계
     * @param {number} index
     */
    function dfs(path, sum, index) {
        if(sum === target){
            answer.push(path);
            return;
        }
        
        for (let i = index; i < candidates.length; i++) {
            const el = candidates[i];
            if(sum + el <= target){
                dfs([...path, el], sum + el, i);
            }
        }
    }

    return answer;
};