4 sum problem

Given an array of integers and a target we have to check if there exists a quadruplets (four elements) in the array such that there sum is equal to the given target. Popularly know as 4 sum problem.

Here is the another example in which we print all the unique quadruplets that are equal to the given sum.

Example

Input:
arr = [1, 2, 3, 5, 6, 11, 15, 16, 17, 18];
sum = 20;

Output:
true
/*
[1, 3, 5, 11]
*/

This is the third question from the series

1. 2 sum
2. 3 sum
3. 4 sum

Naïve brute force approach

We can use 4 nested loops and consider every quadruplets in the given array to check if desired target can be achieved or not.

---

Naïve recursive approach to solve 4 sum problem

Using recursion to solve this problem.

Conceptually this is how it works

• For each item in the array we either consider it or ignore it and recur for the remaining items.
• If the given target can be achieved by summation of quadruplets then return true or else return false.

const fourSum = (arr, n, sum, count) => {
  // if there exists a quadruplets whose sum is equal to the given target
  if (sum == 0 && count == 4) {
	return true;
  }

  // base case, if we cannot find a quadruplets
  if (count > 4 || n == 0) {
        return false;
  }

  // Recur 
  // considering current element or
  // ignoring current element
 return fourSum(arr, n - 1, sum - arr[n - 1], count + 1) || fourSum(arr, n - 1, sum, count);
}

Input:
const arr = [1, 2, 3, 5, 6, 11, 15, 16, 17, 18];
const sum = 20;
console.log(fourSum(arr, arr.length, sum, 0));

Output:
true
[1, 3, 5, 11]

Time complexity: O(2 ^ N) because for each we are calling the same function twice.
Space complexity: O(2 ^ N) considering the call stack, O(1) other wise.

---

Efficient approach using hashing to solve 4 sum problem

Conceptually this is how it works

• Just like 2 sum problem rather than considering single number we will consider a pair.
• Add every pair and with their sum one by one in the Hashmap.
• Then for the current pair check if the remaining target is present in the map or not and if the map has the pending target and its pair of elements are not overlapping with the current pair then quadruplet is found, thus return true otherwise return false.

const fourSumWithHashing = (arr, sum, n = arr.length) => {
  // hashmap
  const map = new Map();
  
  for(let i = 0; i < n - 1; i++){
    for(let j = i + 1; j < n; j++){
      
      // calc pending target sum
      let val = sum - (arr[i] + arr[j]);
      
      // if pending target is present in the map,
      // then there can be a quadruplet
      if(map.has(val)){

        // get all quadruplets whose indexes are not overlapping        
        for(let entries of map.get(val)){
          
          let {x, y} = entries;
          // if Quadruplet don't overlap return true
	  if ((x != i && x != j) && (y != i && y != j)){
	    return true;
	  }
        }
      }
      
      // add current pair
      if(!map.has(arr[i] + arr[j])){
        map.set(arr[i] + arr[j], []);
      }
        
      map.get(arr[i] + arr[j]).push({x: i, y: j});
    }
  }
  
  //return false
  return false;
}

Input:
const arr = [1, 2, 3, 5, 6, 11, 15, 16, 17, 18];
const sum = 20;
console.log(fourSumWithHashing(arr, sum));

Output:
true
[1, 3, 5, 11]

Time complexity: O(n ^ 2).
Space complexity: O(n ^ 2).