0039. Combination Sum.md

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    // Sort the candidates array as otherwise we could 
    // come up with solution [3,2,2] instead of [2,2,3]
    candidates.sort((a,b) =>  a - b);
    
    // Store all possible combinations in here
    let stack = [];
    
     // The recursive part. 
    // target is what we're looking for. This will become smaller, deeper in to the recursive calls
    // res is where we will record our current path
    // i is the index of the numbers we're considering. Once we get stuck with the 2's
    // we will increase i to try other combinations
    function dfs(target, res, i) {
        if (target === 0) {
            stack.push(res);
            return;
        }  else {
             // don't run over the candidates array length 
            // and don't try candidates that would bring target below 0
            while (i < candidates.length && target - candidates[i] >= 0) {
                dfs(target - candidates[i], [...res, candidates[i]], i)
                i++;
            }   
        }
    }
    dfs(target, [], 0);
    return stack;
};