# 4Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/4sum)
Canonical: https://scaleengineer.com/dsa/problems/4sum
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [DoorDash](https://scaleengineer.com/companies/doordash), [Google](https://scaleengineer.com/companies/google), [Infosys](https://scaleengineer.com/companies/infosys), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [tcs](https://scaleengineer.com/companies/tcs), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [oyo](https://scaleengineer.com/companies/oyo), [Cloudflare](https://scaleengineer.com/companies/cloudflare), [Rubrik](https://scaleengineer.com/companies/rubrik), [Zoox](https://scaleengineer.com/companies/zoox)
---
## Problem
Given an array `nums` of `n` integers, return _an array of all the **unique** quadruplets_ `[nums[a], nums[b], nums[c], nums[d]]` such that:

* `0 <= a, b, c, d < n`
* `a`, `b`, `c`, and `d` are **distinct**.
* `nums[a] + nums[b] + nums[c] + nums[d] == target`

You may return the answer in **any order**.

**Example 1:**

**Input:** nums = [1,0,-1,0,-2,2], target = 0
**Output:** [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

**Example 2:**

**Input:** nums = [2,2,2,2,2], target = 8
**Output:** [[2,2,2,2]]

**Constraints:**

* `1 <= nums.length <= 200`
* `-109 <= nums[i] <= 109`
* `-109 <= target <= 109`

# Approaches
## Brute Force with Four Nested Loops
This is the most straightforward but least efficient approach. It involves iterating through every possible combination of four distinct elements in the array and checking if their sum equals the target.
**Time:** O(n^4) · **Space:** O(k), where k is the number of unique quadruplets found. This is for the `HashSet`.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient.; Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
### Explanation
The algorithm iterates through all possible combinations of four distinct indices `i`, `j`, `k`, and `l` using four nested loops. For each combination, it checks if the sum of the elements at these indices equals the `target`. To handle permutations of the same set of numbers as a single unique quadruplet (e.g., `[-1, 0, 0, 1]` is the same as `[0, -1, 1, 0]`), we can sort the input array first. This ensures that when we find a valid quadruplet `(nums[i], nums[j], nums[k], nums[l])` where `i < j < k < l`, it is in a canonical sorted order. We then add this quadruplet to a `HashSet` to automatically handle any duplicates that might arise from different combinations of indices yielding the same values (e.g., if the input has duplicate numbers). Finally, the content of the set is converted to a list and returned. It's important to use a `long` for the sum to prevent potential integer overflow.

```java
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int n = nums.length;
        Set<List<Integer>> resultSet = new HashSet<>();
        Arrays.sort(nums);
        for (int i = 0; i < n - 3; i++) {
            for (int j = i + 1; j < n - 2; j++) {
                for (int k = j + 1; k < n - 1; k++) {
                    for (int l = k + 1; l < n; l++) {
                        long sum = (long) nums[i] + nums[j] + nums[k] + nums[l];
                        if (sum == target) {
                            resultSet.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
                        }
                    }
                }
            }
        }
        return new ArrayList<>(resultSet);
    }
}
```
### Algorithm
- Sort the input array `nums`.
- Create a `HashSet` to store unique quadruplets.
- Use a loop for `i` from `0` to `n-4`.
- Inside, use a loop for `j` from `i+1` to `n-3`.
- Inside, use a loop for `k` from `j+1` to `n-2`.
- Inside, use a loop for `l` from `k+1` to `n-1`.
- Check if `(long) nums[i] + nums[j] + nums[k] + nums[l] == target`.
- If the condition is true, add the list `(nums[i], nums[j], nums[k], nums[l])` to the `HashSet`.
- After the loops, return a new `ArrayList` created from the `HashSet`.

## Sorting with Two-Pointer Technique
This is an efficient approach that leverages sorting to avoid redundant calculations and to easily find the required pairs. It reduces the problem to a 3-Sum problem for each element, which is then further reduced to a 2-Sum problem solved efficiently with two pointers.
**Time:** O(n^3) · **Space:** O(log n) or O(n) for sorting, depending on the implementation. O(1) auxiliary space otherwise (not counting the output list).
**Pros:** Much more efficient than the brute-force approach.; Passes the time limits for typical constraints.; Avoids using extra space for a `Set` by handling duplicates smartly within the loops.
**Cons:** The implementation is more complex than the brute-force approach.; Requires careful handling of pointer movements and duplicate-skipping logic.
### Explanation
The first and most crucial step is to sort the input array `nums`. Sorting allows us to:
1.  Use the two-pointer technique to find pairs with a specific sum in linear time.
2.  Easily skip duplicate elements to ensure the uniqueness of the resulting quadruplets without needing an extra `Set`.

The overall algorithm works by fixing the first two numbers of the quadruplet and then finding the other two.
- We use a main loop to iterate through the array and pick the first number, `nums[i]`.
- A nested loop picks the second number, `nums[j]`.
- For each pair `(nums[i], nums[j])`, our goal is to find two other numbers `nums[left]` and `nums[right]` in the rest of the array (from index `j+1` to `n-1`).
- This is a classic 2-Sum problem on a sorted subarray, which we solve using the two-pointer approach. We initialize `left = j + 1` and `right = n - 1`.
- We then move these pointers inward based on their sum compared to the required sum, until `left` crosses `right`.
- To avoid duplicate quadruplets, we add checks. After finding a valid quadruplet, we advance the `left` and `right` pointers past any subsequent duplicate elements. Similarly, in the outer loops for `i` and `j`, we skip iterations where the current element is the same as the previous one.
- A critical detail is to use `long` for the sum to prevent integer overflow.

```java
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 4) {
            return result;
        }
        int n = nums.length;
        Arrays.sort(nums);

        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates for i
            // Early exit optimizations
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;

            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // Skip duplicates for j
                // Early exit optimizations
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
                if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue;

                int left = j + 1;
                int right = n - 1;
                
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Sort the input array `nums`.
- Initialize an empty list `result`.
- Iterate through the array with index `i` from `0` to `n-4`. Skip duplicates.
- Inside, iterate with index `j` from `i+1` to `n-3`. Skip duplicates.
- Initialize two pointers, `left = j + 1` and `right = n - 1`.
- While `left < right`:
  - Calculate the `sum` of `nums[i]`, `nums[j]`, `nums[left]`, and `nums[right]`.
  - If `sum == target`, add the quadruplet to `result`. Then, move `left` and `right` pointers inward, skipping any duplicate values.
  - If `sum < target`, increment `left`.
  - If `sum > target`, decrement `right`.
- Return the `result` list.

# Solutions
### CSharp

```csharp
public class Solution {
    public IList < IList < int >> FourSum(int[] nums, int target) {
        int n = nums.Length;
        var ans = new List < IList < int >> ();
        if (n < 4) {
            return ans;
        }
        Array.Sort(nums);
        for (int i = 0; i < n - 3; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < n - 2; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int k = j + 1, l = n - 1;
                while (k < l) {
                    long x = (long) nums[i] + nums[j] + nums[k] + nums[l];
                    if (x < target) {
                        ++k;
                    } else if (x > target) {
                        --l;
                    } else {
                        ans.Add(new List < int > {
                            nums[i],
                            nums[j],
                            nums[k++],
                            nums[l--]
                        });
                        while (k < l && nums[k] == nums[k - 1]) {
                            ++k;
                        }
                        while (k < l && nums[l] == nums[l + 1]) {
                            --l;
                        }
                    }
                }
            }
        }
        return ans;
    }
}
```

### Java

```java
class Solution { public List < List < Integer >> fourSum ( int [] nums , int target ) { int n = nums . length ; List < List < Integer >> ans = new ArrayList <>(); if ( n < 4 ) { return ans ; } Arrays . sort ( nums ); for ( int i = 0 ; i < n - 3 ; ++ i ) { if ( i > 0 && nums [ i ] == nums [ i - 1 ]) { continue ; } for ( int j = i + 1 ; j < n - 2 ; ++ j ) { if ( j > i + 1 && nums [ j ] == nums [ j - 1 ]) { continue ; } int k = j + 1 , l = n - 1 ; while ( k < l ) { long x = ( long ) nums [ i ] + nums [ j ] + nums [ k ] + nums [ l ]; if ( x < target ) { ++ k ; } else if ( x > target ) { -- l ; } else { ans . add ( List . of ( nums [ i ], nums [ j ], nums [ k ++], nums [ l --])); while ( k < l && nums [ k ] == nums [ k - 1 ]) { ++ k ; } while ( k < l && nums [ l ] == nums [ l + 1 ]) { -- l ; } } } } } return ans ; } } // // general solution, k-sum // https://leetcode.com/problems/4sum/solution/ // below kSum() divide-and-conquer idea is good, but not passing Online-Judge class Solution { public List < List < Integer >> fourSum ( int [] nums , int target ) { Arrays . sort ( nums ); return kSum ( nums , target , 0 , 4 ); } public List < List < Integer >> kSum ( int [] nums , int target , int start , int k ) { List < List < Integer >> res = new ArrayList <>(); if ( start == nums . length || nums [ start ] * k > target || target > nums [ nums . length - 1 ] * k ) return res ; if ( k == 2 ) return twoSum ( nums , target , start ); for ( int i = start ; i < nums . length ; ++ i ) if ( i == start || nums [ i - 1 ] != nums [ i ]) // 'i == start' is key, since it could be in a following recurion of [1,1,1] where start is 3rd '1' for ( List < Integer > set : kSum ( nums , target - nums [ i ], i + 1 , k - 1 )) { res . add ( new ArrayList <>( Arrays . asList ( nums [ i ]))); res . get ( res . size () - 1 ). addAll ( set ); } return res ; } public List < List < Integer >> twoSum ( int [] nums , int target , int start ) { List < List < Integer >> res = new ArrayList <>(); int lo = start , hi = nums . length - 1 ; while ( lo < hi ) { int sum = nums [ lo ] + nums [ hi ]; if ( sum < target || ( lo > start && nums [ lo ] == nums [ lo - 1 ])) ++ lo ; else if ( sum > target || ( hi < nums . length - 1 && nums [ hi ] == nums [ hi + 1 ])) -- hi ; else res . add ( Arrays . asList ( nums [ lo ++], nums [ hi --])); } return res ; } } public class Four_Sum { public static void main ( String [] args ) { Four_Sum out = new Four_Sum (); Solution s = out . new Solution (); // SolutionForLoop s= out.new SolutionForLoop(); List < List < Integer >> result = s . fourSum ( new int []{ 1 , 0 , - 1 , 0 , - 2 , 2 }, 0 ); for ( List < Integer > each : result ) { String one = "" ; for ( int e : each ) { one = one + " " + e ; } System . out . println ( one ); } } // time: O(NlogN) // space: O(1) public class Solution { public List < List < Integer >> fourSum ( int [] nums , int target ) { List < List < Integer >> list = new ArrayList <>(); if ( nums . length < 4 ) { return list ; } Arrays . sort ( nums ); // improved based on 3-sum int layer4 = 0 ; while ( layer4 < nums . length ) { // @note: below is causing me trouble when convert for to while // in while, here "layer4" is never updated for case like {0,0,0,0} // if(layer4 > 0 && nums[layer4] == nums[layer4 - 1]) continue; if ( layer4 > 0 && nums [ layer4 ] == nums [ layer4 - 1 ]) { layer4 ++; } // hold one pointer, other two pointer moving int ancher = layer4 + 1 ; while ( ancher < nums . length ) { int i = ancher + 1 ; int j = nums . length - 1 ; while ( i < j ) { int sum = nums [ layer4 ] + nums [ ancher ] + nums [ i ] + nums [ j ]; if ( sum == target ) { // @note: Arrays.asList() list . add ( Arrays . asList ( nums [ layer4 ], nums [ ancher ], nums [ i ], nums [ j ])); // @note: dont forget move pointers i ++; j --; // @note: optimization. above i,j is updated already, compare with previous position while ( i < j && nums [ i ] == nums [ i - 1 ]) { i ++; } while ( j > i && nums [ j ] == nums [ j + 1 ]) { j --; } } else if ( sum < target ) { i ++; // @note: same here, possibly updated already, note i-1 or i+1 while ( i < j && nums [ i ] == nums [ i - 1 ]) { i ++; } } else { j --; // @note: same here, possibly updated already, note i-1 or i+1 while ( j > i && j + 1 < nums . length && nums [ j ] == nums [ j + 1 ]) { j --; } } } ancher ++; // optimize for 2nd pointer while ( ancher > layer4 && ancher < nums . length && nums [ ancher ] == nums [ ancher - 1 ]) { ancher ++; } } layer4 ++; // optimize for 2nd pointer while ( layer4 < nums . length && nums [ layer4 ] == nums [ layer4 - 1 ]) { layer4 ++; } } return list ; } } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} target * @return {number[][]} */ var fourSum =
  function (nums, target) {
    const n = nums.length;
    const ans = [];
    if (n < 4) {
      return ans;
    }
    nums.sort((a, b) => a - b);
    for (let i = 0; i < n - 3; ++i) {
      if (i > 0 && nums[i] === nums[i - 1]) {
        continue;
      }
      for (let j = i + 1; j < n - 2; ++j) {
        if (j > i + 1 && nums[j] === nums[j - 1]) {
          continue;
        }
        let [k, l] = [j + 1, n - 1];
        while (k < l) {
          const x = nums[i] + nums[j] + nums[k] + nums[l];
          if (x < target) {
            ++k;
          } else if (x > target) {
            --l;
          } else {
            ans.push([nums[i], nums[j], nums[k++], nums[l--]]);
            while (k < l && nums[k] === nums[k - 1]) {
              ++k;
            }
            while (k < l && nums[l] === nums[l + 1]) {
              --l;
            }
          }
        }
      }
    }
    return ans;
  };

```

### CPP

```cpp
class Solution { public: vector < vector < int >> fourSum ( vector < int >& nums , int target ) { int n = nums . size (); vector < vector < int >> ans ; if ( n < 4 ) { return ans ; } sort ( nums . begin (), nums . end ()); for ( int i = 0 ; i < n - 3 ; ++ i ) { if ( i && nums [ i ] == nums [ i - 1 ]) { continue ; } for ( int j = i + 1 ; j < n - 2 ; ++ j ) { if ( j > i + 1 && nums [ j ] == nums [ j - 1 ]) { continue ; } int k = j + 1 , l = n - 1 ; while ( k < l ) { long long x = ( long long ) nums [ i ] + nums [ j ] + nums [ k ] + nums [ l ]; if ( x < target ) { ++ k ; } else if ( x > target ) { -- l ; } else { ans . push_back ({ nums [ i ], nums [ j ], nums [ k ++ ], nums [ l -- ]}); while ( k < l && nums [ k ] == nums [ k - 1 ]) { ++ k ; } while ( k < l && nums [ l ] == nums [ l + 1 ]) { -- l ; } } } } } return ans ; } };
```

### Python

```python
# k-sum class Solution : def fourSum ( self , nums : List [ int ], target : int ) -> List [ List [ int ]]: nums . sort () return self . kSum ( nums , target , 0 , 4 ) def kSum ( self , nums : List [ int ], target : int , start : int , k : int ) -> List [ List [ int ]]: res = [] if start == len ( nums ) or nums [ start ] * k > target or target > nums [ - 1 ] * k : return res if k == 2 : return self . twoSum ( nums , target , start ) for i in range ( start , len ( nums )): if i == start or nums [ i - 1 ] != nums [ i ]: # here is a hidden matching target==0 # if not matching target, then kSum() will return empty list for sset in self . kSum ( nums , target - nums [ i ], i + 1 , k - 1 ): # if kSum(k-1) return empty, it will not execute this line res . append ([ nums [ i ] ] + sset ) # put nums[i] in a list return res def twoSum ( self , nums : List [ int ], target : int , start : int ) -> List [ List [ int ]]: res = [] lo , hi = start , len ( nums ) - 1 while lo < hi : s = nums [ lo ] + nums [ hi ] if s < target or ( lo > start and nums [ lo ] == nums [ lo - 1 ]): lo += 1 elif s > target or ( hi < len ( nums ) - 1 and nums [ hi ] == nums [ hi + 1 ]): hi -= 1 else : res . append ([ nums [ lo ], nums [ hi ]]) # continue searching, could be multiple answers lo += 1 hi -= 1 return res ######### class Solution : def fourSum ( self , nums : List [ int ], target : int ) -> List [ List [ int ]]: n = len ( nums ) ans = [] if n < 4 : return ans nums . sort () for i in range ( n - 3 ): if i and nums [ i ] == nums [ i - 1 ]: continue for j in range ( i + 1 , n - 2 ): if j > i + 1 and nums [ j ] == nums [ j - 1 ]: continue k , l = j + 1 , n - 1 while k < l : x = nums [ i ] + nums [ j ] + nums [ k ] + nums [ l ] if x < target : k += 1 elif x > target : l -= 1 else : ans . append ([ nums [ i ], nums [ j ], nums [ k ], nums [ l ]]) k , l = k + 1 , l - 1 while k < l and nums [ k ] == nums [ k - 1 ]: k += 1 while k < l and nums [ l ] == nums [ l + 1 ]: l -= 1 return ans
```