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

do{left++;}while(left < right && nums[left] == nums[left-1]);
do{right--;}while(left < right && nums[right] == nums[right+1]);

while(j + 1 < size && nums[j] == nums[j+1])  j++;

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 |
:::

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