[1주차] 풀이공유

[hyunahOh]

var combinationSum = function(candidates, target) {
    const answer = [];
    candidates.forEach((candidate, index) => {
        const nextTarget = target - candidate;
        if (nextTarget === 0) {
            answer.push([target]);
        }
        if (nextTarget > 0) {
            combinationSum(candidates.slice(index), nextTarget).forEach((partialSum) => {
                answer.push([candidate, ...partialSum])
            })
        }
    })

    return answer;
};

[Choozii]

Runtime | Memory 66 ms | 48 MB

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */

let res;

var combinationSum = function(candidates, target) {

    res = []; 

    const backtrack = (sum, selected ,idx) => {
        if(sum === target){            
            res.push(selected);
            return;
        }

        else if(sum > target){
            return;
        } 

        for(let i=idx; i<candidates.length;i++){
            selected.push(candidates[i]);
            sum += candidates[i];
            backtrack(sum, [...selected], i);
            selected.pop();
            sum -= candidates[i];
        }
    }

    backtrack(0, [], 0);
    return res;
};

[intothedeep]

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */

let answer = [];
var combinationSum = function(candidates, target) {
    answer = [];
    // combination?
    const arr = findCombination(candidates, 0, target);
    return answer;
};

function findCombination(arr, idx, target, currArr = [], currSum = 0) {
    for (let i = idx; i < arr.length; i++) {
        const curr = arr[i];
        if (currSum === target) {
            answer.push(currArr);
            break;
        } else if (currSum > target) {
            continue;
        } else if (currSum < target) {
            findCombination(arr, i, target, [...currArr, curr], currSum + curr);
        }
    }

}