---
# System prepended metadata

title: '[LeetCode 18. 4Sum](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/610/week-3-july-15th-july-21st/3816/)'

---

# [LeetCode 18. 4Sum](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/610/week-3-july-15th-july-21st/3816/)
### Daily challenge Jul 16, 2021 (MEDIAN)

>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**.


:::info
**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]]
:::

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


:::warning
**Constraints:**
* 1 <= nums.length <= 200
* -109 <= nums[i] <= 109
* -109 <= target <= 109
:::

---



### Approach 1 : Two Pointer :book: 
**`40 ms ( 84.35% )`**  **`O(N^3)`**


>nums = **[1,0,-1,0,-2,2,5]** ; target = **0**

When `i, j` are fixed, **`taget2`** `= 0 - (-2) - (-1)` **`= 3`**.
Let **`left = j + 1`**, **`right = nums.size() - 1`**.
 
>* If nums[left] + nums[right] **`>`** target2 ---> `right - 1`
>* If nums[left] + nums[right] **`<`** target2 ---> `left + 1`
>* If nums[left] + nums[right] **`==`** target2 ---> `Got one answer` :100: 
>>**`{nums[i], num[j], nums[left], nums[right]}`** is the answer.
:::danger
Because we need to find all the **unique** answers, elements which are equal to current answer have to **skip**.
```cpp=19
do{left++;}while(left < right && nums[left] == nums[left-1]);
do{right--;}while(left < right && nums[right] == nums[right+1]);
```
```cpp=25
while(j + 1 < size && nums[j] == nums[j+1])  j++;
```
```cpp=27
while(i + 1 < size && nums[i] == nums[i+1])  i++;
```
:::

:::success
:+1: **EASY EXAMPLE :**  

**1.** nums[left] + nums[right] = **5 > taget2** ---> **`right - 1`**

| -2 | -1 | 0 | 0 | 1 | 2 | 5
| :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: |
| i | j | left |  |  |  | right |


**2.** nums[left] + nums[right] = **2 < taget2** ---> **`left + 1`**

| -2 | -1 | 0 | 0 | 1 | 2 | 5
| :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: |
| i | j | left |  |  | right |  |

**3.** nums[left] + nums[right] = **2 < taget2**  ---> **`left + 1`**

| -2 | -1 | 0 | 0 | 1 | 2 | 5
| :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: |
| i | j |  | left |  | right |

**4.** nums[left] + nums[right] = **3 == taget2**  ---> **`GOT THE ANSWER`** :100: 

| -2 | -1 | 0 | 0 | 1 | 2 | 5
| :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: |
| i | j |  |  | left | right |

**5.** When left >= right ---> **Next loop**

| -2 | -1 | 0 | 0 | 1 | 2 | 5
| :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: |
| i |  | j | left |  |  | right |
:::


```cpp=1
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int size = nums.size();
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        
        for(int i=0; i<size-3; i++){
            int target3 = target - nums[i];
            for(int j=i+1; j<size-2; j++){
                int target2 = target3 - nums[j];
                int left = j + 1, right = size-1;
                
                while(left < right){
                    int sum2 = nums[left] + nums[right];
                    if(sum2 == target2){
                        ans.push_back(vector<int>({nums[i], nums[j], nums[left], nums[right]}));
                        
                        do{left++;}while(left < right && nums[left] == nums[left-1]);
                        do{right--;}while(left < right && nums[right] == nums[right+1]);
                    }
                    else if(sum2 > target2) right--;
                    else if(sum2 < target2) left++;          
                }
                while(j + 1 < size && nums[j] == nums[j+1])  j++;
            }
            while(i + 1 < size && nums[i] == nums[i+1])  i++;
        }
        return ans;
    }
};
```

### Approach 2 : KSums General Solution :book: 
**` ms ( % )`**  **`O()`**

DISCRIPTION

> EXAMPLE


```cpp=1

```