Array Quadruplet

array-quadruplet.js

var arr = [0, 0, 0, 1, 2, 5, 6, 7, 8, 9, 11, 16, 18, 19, 20, 21, 24, 25, 26, 28, 30, 32, 33, 35, 38, 43, 45, 46, 49, 50, 54, 55, 59, 63, 64, 65, 68, 69, 72, 75, 76, 79, 80, 81, 83, 86, 87, 88, 89, 90, 94, 96, 98, 99];
var s = 387;
// var arr = [5, 5, 5, 5];
// var s = 20;

console.log(findArrayQuadruplet(arr,s));

function findArrayQuadruplet(arr, sum) {
  if (arr.length < 4) return [];
  var new_arr = cleanArray(arr, sum);
  var four_pair = getFourPair(new_arr, sum);
  if (four_pair.length != 4)  return [];
  var result = [new_arr[four_pair[0]], new_arr[four_pair[1]], new_arr[four_pair[2]], new_arr[four_pair[3]]].sort();
  return result;
}

function cleanArray(arr, sum) {
  var new_arr = arr.filter((num)=>{ return num <= sum});
  return new_arr.sort();
}

function getTwoPair(arr,sum) {
  var two_pair = {};
  for (var num1 in arr) {
    for (var num2 in arr) {
      if (num1 >= num2) continue
      var two_sum = arr[num1] + arr[num2];      
      if (two_sum > sum) continue;
      if (two_pair[two_sum] === undefined) {
        two_pair[two_sum] = [[num1, num2]];        
      } else {
        two_pair[two_sum].push([num1, num2]);
      }
    }
  }
  return two_pair;
}

function getFourPair(arr, sum) {
  var two_pair = getTwoPair(arr, sum);
  var temp_arr = [];
  for(var pair in two_pair) {
    temp_arr.push(parseInt(pair));
  }
  var length = temp_arr.length;
  var j = length - 1;
  for(var i = 0; i <= length -1; i++) {
    for (; j >= 0; j--) {
      if (j < i) return [];
      var four_sum = temp_arr[i] + temp_arr[j];
      if (four_sum == sum) {
        // check if index duplicate
        var result = checkTwoPairIndex(two_pair, temp_arr, [i,j]);
        if (result.length == 4) {
          return result;
        }
      }
      if (four_sum > sum) {
        continue;
      } else { // if (four_sum < sum)
        break;
      }
    }
  }
  return [];
}

function checkTwoPairIndex(twoPair, tempArr, match) {
  var match1 = tempArr[match[0]].toString();
  var match2 = tempArr[match[1]].toString();
  for(var match1Result in twoPair[match1]) {
    for(var match2Result in twoPair[match2]) {
      var concatArr = twoPair[match1][match1Result].concat(twoPair[match2][match2Result].filter((item)=>{
        return twoPair[match1][match1Result].indexOf(item) < 0;
      }))
      if (concatArr.length == 4)
        return concatArr;
      continue;
    }
  }
  return [];
}