Javascript, solution-sharing, backtracking


  • 0
    C
    [javascript]
    
    /**
     * step 1: nums.length<3; return [];
     * step 2: every element can only be used once // var used=[]; if(used[i]){ continue ;}else{ used[i]=true; excute; }
     * step 3: [-1, -1, 2] [-1, 2, -1] [2, -1, -1], the same, // Elements in a solution (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
     * step 4: backTracking function
     */
    var threeSum = function(nums) {
        if(nums.length<3) { return []; } // step 1
        nums.sort(function(val1,val2) {
            return val1>val2?1:val1<val2?-1:0;
        });
        // console.log(nums);
        var solution = [];
        var result = [];
        var used = [];
        var backTracking = function(m, n){ // step 4
            if(m==n){
                // console.log(solution);
                if(solution[0]+solution[1]+solution[2]===0){
                    return result.push(solution.slice(0));
                }
                return false;
            }else{
                var last_num;
                for(var i=0; i<nums.length; i++){
                    if(used[i]) { continue; } // step 2
                    if(last_num==nums[i]) { continue; }
                    if(m>0 && solution[m-1]>nums[i]) { continue; } // step 3
                    used[i] = true;
                    last_num = nums[i];
                    solution[m] = nums[i];
                    arguments.callee(m+1, n);
                    used[i] = false;
                }
            }
        }
        backTracking(0, 3);
        return result;
    };

Log in to reply
 

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