39. Combination Sum - 쉬운설명 반복문 사용

39. 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.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

 

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2: 

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3: 

Input: candidates = [2], target = 1
Output: []

 

계획

문제 해결 전략

 

Example 1의 예시를 아래에서 살펴보겠습니다. 

 

 

구현 전략

 

DFS를 이용하여 풀어줄 계획입니다. 그리고 target보다 클경우 더이상 child로 접근하지 않도록 합니다. 

 

해설

var combinationSum = function(candidates, target) {
    let result = []
    
    findCombination(); 
    return result
    
    function findCombination(start = 0, sum =0, ans = []){
        if(sum > target) return; 
        if(sum === target){
            result.push(ans.slice());
        }
        
        for(let i=start; i<arr.length; i++){
            findCombination(i, sum + arr[i], [...ans, arr[i]]);
        }
    }
};