Four Sum Problem

In this article, we will be solving a commonly asked question on arrays which is the 4 sum problem. In this problem, we are given an array of N integers and a target integer. We aim to find four elements in the array whose sum is equal to the target.

Example:

N = 6

Arr = [1, 0, -1, 0, -2, 2]

Target = 0 

Output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

The output is a list of unique quadruplets that sum up to the target.

Solution:

Explanation

This function finds all unique quadruplets in an array that sum up to a given target. The approach is to use a sorted array and two nested loops to fix the first two numbers, then use a two-pointer technique to find the remaining two numbers that complete the quadruplet.

1.    Sort the array to easily handle duplicates and use the two-pointer technique.

2.    Use two nested loops to select the first two numbers.

3.    Then we are using wo-pointer technique to find the remaining two numbers that sum up to the target.

4.    Skip duplicates to ensure that only unique quadruplets are included in the result.

Time Complexity: O(n^3)

Space Complexity: O(1)