Combination Sum

combinationSum.js

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    let answer = [];
    let stack = [];
    let findCombinations = (index, targetToFind, stack, answer, candidates) => {
        if(index === candidates.length) {
            if(targetToFind === 0) {
                answer.push([...stack]);
            }
            return;
        }
        if(targetToFind === 0) {
            answer.push([...stack]);
            return;
        }
        if(candidates[index] <= targetToFind) {
            stack.push(candidates[index])
            findCombinations(index, targetToFind - candidates[index], stack, answer, candidates);
            stack.pop();
        }
        findCombinations(index + 1, targetToFind, stack, answer, candidates);
    }

    findCombinations(0, target, stack, answer, candidates);
    return answer;
};


// Backtraking
// explanation: https://www.youtube.com/watch?v=OyZFFqQtu98