-2

Here my code to solve the 4sum question in leetcode

var fourSum = function(ns, tar) {
    ns.sort((a, b) => a-b);

    let res=[], out=false;
    for(let i=0; i<ns.length-3; i++) {
        if(ns[i] !== ns[i-1]) {
            out = threeSum(ns, i+1, tar-ns[i]);

            for(let item of out) {
                res.push([ns[i], ...item]);
            }
        }
    }

    return res;
};

var threeSum = function(ns, ind, tar) {
    let res=[], out=false;
    for(let i=ind; i<ns.length-2; i++) {
        if(ns[i] !== ns[i-1]) {
            out = twoSum(ns, i+1, tar-ns[i]);

            for(let item of out) {
                res.push([ns[i], ...item]);
            }
        }
    }

    return res;
}

var twoSum = function(ns, ind, tar) {    
    let set = new Set();
    let res = [];
    for(let i=ind; i<ns.length; i++) {
        if(set.has(tar-ns[i])) {
            res.push([tar-ns[i], ns[i]]);
            while(ns[i] === ns[i+1]) i++;
        } else {
            set.add(ns[i]);
        }    
    }

    return res;
}

Currently it is not able to pass 

case 1:
[0, 0, 0, 0]
0

if I remove if(ns[i] !== ns[i-1]) { It is able to pass case 1, but fail at

case 2:
[-3,-2,-1,0,0,1,2,3]
0
kenpeter
  • 7,404
  • 14
  • 64
  • 95
  • 1
    See this lovely [debug](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) blog for help. Try tracing the logic as you traverse your multi-level solution. I believe you'll get help more readily if you document your approach, use meaningful variable names, etc. – Prune Jul 23 '19 at 17:41

2 Answers2

0

I went through the test case: [0, 0, 0, 0], sum==0 again.

If i ===0, when landing on this if(ns[i] !== ns[i-1]) {

it becomes if(ns[0] !== ns[0-1]) {

out = threeSum(ns, i+1, tar-ns[i]); is able to execute.

Basically, it means the 1st num in each ?Sum needs to be ignored

So I made the following changes in 3sum func

if(i-1 >= ind && ns[i] === ns[i-1]) continue;

Full code:

var fourSum = function(ns, tar) {
    ns.sort((a, b) => a-b);

    let res=[], out=false;
    for(let i=0; i<ns.length-3; i++) {
        // can get in
        if(ns[i] !== ns[i-1]) {            
            out = threeSum(ns, i+1, tar-ns[i]);

            // each set add ns[i], 4 # now
            for(let item of out) {
                res.push([ns[i], ...item]);
            }
        }
    }

    return res;
};

var threeSum = function(ns, ind, tar) {
    let res=[], out=false;
    for(let i=ind; i<ns.length-2; i++) {
        if(i-1 >= ind && ns[i] === ns[i-1]) continue;

        out = twoSum(ns, i+1, tar-ns[i]);

        for(let item of out) {
            res.push([ns[i], ...item]);
        }
    }

    return res;
}

var twoSum = function(ns, ind, tar) {    
    let set = new Set();
    let res = [];
    for(let i=ind; i<ns.length; i++) {
        if(set.has(tar-ns[i])) {
            res.push([tar-ns[i], ns[i]]);
            while(ns[i] === ns[i+1]) i++;
        } else {
            set.add(ns[i]);
        }    
    }

    return res;
}
kenpeter
  • 7,404
  • 14
  • 64
  • 95
-1

Why not just use 4 for loops to solve this ? Basically you take 4 loops for each a,b,c and d. Then if they sum up to the target value you just add them to the result array called res (in increasing order).

At the end you just have to make sure that res has only unique values. For that you can take a look at this answer which converts the arrays to string and then checks for duplicates and removes the duplicates.

Here is my accepted solution : 

var fourSum = function(nums, target) {

    var res = [];
    for(var a=0; a < nums.length; a++){
        for(var b=a+1; b < nums.length; b++){
            for(var c=b+1; c < nums.length; c++){
                for(var d=c+1; d < nums.length; d++){
                    if(nums[a] + nums[b] + nums[c] + nums[d] == target){
                        res.push( [nums[a], nums[b], nums[c], nums[d]].sort() )
                    }
                }
            }
        }
    }

    var res_set  = new Set(res.map(JSON.stringify));
    var res_uniq = Array.from(res_set).map(JSON.parse);

    return res_uniq;
};
DollarAkshay
  • 2,063
  • 1
  • 21
  • 39