> For the complete documentation index, see [llms.txt](https://joshualbarb.gitbook.io/leetcode-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joshualbarb.gitbook.io/leetcode-problems/hash-table/4sum.md).

# 4Sum

## Problem

Given an array `nums` of *n* integers and an integer `target`, are there elements *a*, *b*, *c*, and *d* in `nums` such that *a* + *b* + *c* + *d* = `target`? Find all unique quadruplets in the array which gives the sum of `target`.

**Notice** that the solution set must not contain duplicate quadruplets.

{% hint style="info" %}
For example:

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

{% endhint %}

## Solution

```
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:	
        soln = []
        nums = sorted(nums)
        
        for i in range(len(nums)-3):
            if i!=0 and nums[i] == nums[i-1]:
                continue
            for j in range(i+1, len(nums)-2):
                if j != i+1 and nums[j] == nums[j-1]:
                    continue
                left = j+1
                right = len(nums)-1
                
                while left < right:
                    currentSum = nums[i]+nums[j]+nums[left]+nums[right]
                    if currentSum < target:
                        left+=1
                    elif currentSum > target:
                        right-=1
                    else:
                        soln.append([nums[i], nums[j], nums[left], nums[right]])
                        left+=1
                        right-=1
                
                        while left < right and nums[left] == nums[left-1]:
                            left+=1
                        
                        while left < right and nums[right] == nums[right+1]:
                            right-=1
                    
        return soln
                    

#Time: O(n^3)
#Space: O(1)
```