39. Combination Sum javascript leetcode

문제정보

요약하자면 다음과 같습니다.
1. 정수를 담은 배열 candidates , 정수 target이 매개변수로 주어짐
2. candidates의 배열요소들을 조합해 target값을 만들 수 있는 경우의 수를 모두 return할 것
3. output은 2차원배열형태로 return

다양한 솔루션이 있겠지만 저는 재귀를 통한 방법을 선택했습니다.

나의풀이(가 아닌)

var combinationSum = function(candidates, target) {
    let index = 0
    let tempDataStruct = []
    let result = []

    function backtracking(index, target, tempDataStruct) {
        if(target === 0) {
            result.push([...tempDataStruct])
            return
        }
    
        if(target < 0) return;
    
        for(let i=index; i<candidates.length; i++) {
            tempDataStruct.push(candidates[i])
            backtracking(i, target-candidates[i], tempDataStruct)
            tempDataStruct.pop()
        }
    }
    backtracking(index, target, tempDataStruct)
    return result;
};

다른사람의 풀이를 참고했습니다.
저번에 재귀를 공부하면서 봤던 순열 코드와 비슷한 구성인데
push / pop을 이용해 종료조건을 향해 달려가는 구조를 만들고
꼬리재귀형태로 구현하기 위해 답을 저장해줄 매개변수를 선언

연산이 끝나면 [...]연산자를 이용해서 배열 통째로 push해주는 코드입니다.

https://blog.naver.com/cardiba/222923846408

자세한 구조는
제가 네이버블로그에 열심히 정리한 재귀함수의 이해 포스팅을 보시는걸 추천드려요.

코드설명

var combinationSum = function(candidates, target) {
    let index = 0
    let tempDataStruct = []
    let result = []
// 재귀 함수에 사용할 변수들과 답을 저장할 변수를 선언해줍니다.
// 우리는 index를 0으로 재활용하길 원하기 때문에 반복 바깥에서 index를 지정해줍니다.

    function backtracking(index, target, tempDataStruct) {
        if(target === 0) {
            result.push([...tempDataStruct])
            return
        }
//재귀의 종료 조건 target값이 0이 되면 result 변수에 답을 배열 채로 push합니다.

        if(target < 0) return;
//  target - candidates[i]를 하는 과정에서 빈번하게 target값이 음수가 되는 케이스가 발생합니다.
//  그럴 경우 그냥 반환해주고 다음 재귀 or for문으로 넘어가기 위한 종료 조건입니다.

        for(let i=index; i<candidates.length; i++) {
            tempDataStruct.push(candidates[i])
            backtracking(i, target-candidates[i], tempDataStruct)
// target값이 0이거나 0보다 작아질 때까지 계속 호출되고 i = index이므로 i는 계속 0으로 초기화됩니다.
// 즉 처음 loop에서 재귀가 계속 호출되며 8 - 2 = 6 -> 6 - 2 -> 4 - 2 -> 2 -> 2 - 2 == 0 재귀 stop
// [2,2,2,2] 가 return 됩니다. 
            tempDataStruct.pop()
// 재귀 호출이 끝나고 i++ 하기 전 배열을 이전 요소들을 pop해줍니다.
        }
    }
    backtracking(index, target, tempDataStruct)
// backtracking function은 combinationsum function 안의 function이므로 사용을 위해서 호출해줍니다.
    return result;
//backtracking 호출 후 얻은 result를 return합니다.
};

다른 사람의 Cool한 풀이

https://duncan-mcardle.medium.com/leetcode-problem-39-combination-sum-javascript-389a8a9f884

var combinationSum = function (nums, target) {
    let combinations = [];
    nums.sort((a, b) => a - b);

    function backtrack(tempList, remaining, start) {
        for (let i = start; i < nums.length && nums[i] <= remaining; i++) {
            if (nums[i] === remaining) {
                combinations.push([...tempList, nums[i]]);
            } else {
                backtrack([...tempList, nums[i]], remaining - nums[i], i);
            }
        }
    }

    backtrack([], target, 0);
    return combinations;
};

사전에 nums를 오름차순으로 정렬해주면 더 효율좋은 코드를 구성할 수 있다.
까지만 이해했습니다.

자세한 설명은 위 블로그 링크에 친절하게 설명되어있으니
관심가는 분들은 참고해보시길..