[리트코드] 39. Combination Sum

문제

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

Combination Sum - LeetCode

 

 

소스코드

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

 

이문제는 코드를 보고 어떻게 돌아가는지 설명을 보시면 이해가 가실 것 같아요

보이실지 잘 모르겠는데

condidates = [2, 3, 6], target=7일 경우에 돌아가는 구조입니다.

 

var combinationSum = function(candidates, target) {
    let result = [];
        
    function sumTarget(arr=[], sum=0, idx=0){
        if(sum > target) return;
        if(sum === target){
            result.push(arr);
            return;
        }
        
        for(let i= idx; i<candidates.length; i++){
            console.log([...arr, candidates[i]], sum+candidates[i], i)
            sumTarget([...arr, candidates[i]], sum+candidates[i], i);
        }
    }
    sumTarget();
    return result;
}; []

이렇게 중간에 콘솔을 찍어보면

[ 2 ] 2 0
[ 2, 2 ] 4 0
[ 2, 2, 2 ] 6 0
[ 2, 2, 2, 2 ] 8 0
[ 2, 2, 2, 3 ] 9 1
[ 2, 2, 2, 6 ] 12 2
[ 2, 2, 3 ] 7 1
[ 2, 2, 6 ] 10 2
[ 2, 3 ] 5 1
[ 2, 3, 3 ] 8 1
[ 2, 3, 6 ] 11 2
[ 2, 6 ] 8 2
[ 3 ] 3 1
[ 3, 3 ] 6 1
[ 3, 3, 3 ] 9 1
[ 3, 3, 6 ] 12 2
[ 3, 6 ] 9 2
[ 6 ] 6 2
[ 6, 6 ] 12 2

이런식으로 나오고

 

나누어서 설명하면 아래와 같이 되겠죠

[ 2 ] 2 0
[ 2, 2 ] 4 0
[ 2, 2, 2 ] 6 0
[ 2, 2, 2, 2 ] 8 0

[ 2, 2, 2, 3 ] 9 1
[ 2, 2, 2, 6 ] 12 2
[ 2, 2, 3 ] 7 1
[ 2, 2, 6 ] 10 2
[ 2, 3 ] 5 1
[ 2, 3, 3 ] 8 1
[ 2, 3, 6 ] 11 2
[ 2, 6 ] 8 2

[ 3 ] 3 1
[ 3, 3 ] 6 1
[ 3, 3, 3 ] 9 1
[ 3, 3, 6 ] 12 2
[ 3, 6 ] 9 2

[ 6 ] 6 2
[ 6, 6 ] 12 2

---