0040. Combination Sum II.md

DFS

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    let stack = [];
    candidates.sort((a, b) => a - b);
    
    function dfs(target, res, i) {
        if(target === 0) {
            stack.push(res);
            return;
        } else {
            while(i < candidates.length && target - candidates[i] >= 0) {
                 // increase i with 1 in the next round as we're not allowed to reuse
                dfs(target - candidates[i], [...res, candidates[i]], i + 1);
                i++;
                // extra increase in case we're dealing with dupes. No new path should start with the one
                // we just picked off below
                while (candidates[i - 1] === candidates[i]) {
                    i++;
                }
            }
        }
    }
    
    dfs(target, [], 0);
    return stack;
};