JavaScript solution with DFS


  • 1
    L
    function combinationSum2(candidates, target) {
        var res = []; // [][]
        var prefix = [];
    
        candidates.sort((a, b) => a - b);
        search(0, target);
        return res;
    
        function search(idx, rest) {
            if (rest === 0 && idx === candidates.length) {
                return res.push(prefix.slice());
            }
    
            if (rest < 0 || idx === candidates.length) {
              return;
            }
    
            // include number at idx
            prefix.push(candidates[idx]);
            search(idx + 1, rest - candidates[idx]);
            
            // exclude number at idx
            // eg. [1, 1, 1]
            // allow 
            // [1, 1, 1]
            // [X, 1, 1]
            // [X, X, 1]
            // [X, X, X]
            // disallow
            // [1, 1, X]
            // [1, X, X]
            prefix.pop();
            if (prefix[prefix.length - 1] !== candidates[idx]) {
                search(idx + 1, rest);
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.