# 4sum Problem Leetcode – Python Solutions

LeetCode has a Medium coding Problem in Its’ Algorithm Section “4sum problem Leetcode”. Today We are going to solve this problem. LeetCode Link of the Problem is HERE

#### Question

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.

#### Examplesto 4sum problem leetcode

```Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
```
```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`

#### 4sum problem leetcodeSolution

The Skeleton Code given in Leetcode is

``````class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""``````

Firstly, Sort the given array of integers. Create a variable result that will store the list containing values of output. Create another variable lookup, which will have keys as the addition of two numbers and values as a list having a position of two numbers when added and give the key.

``````class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums, result, lookup = sorted(nums), [], collections.defaultdict(list)
``````

Secondly, Run two loops one starting from the start of the integers array and one starting from the second element. Fill up the values in the lookup dictionary.

``````class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums, result, lookup = sorted(nums), [], collections.defaultdict(list)
for i in xrange(0, len(nums) - 1):
for j in xrange(i + 1, len(nums)):
is_duplicated = False
for [x, y] in lookup[nums[i] + nums[j]]:
if nums[x] == nums[i]:
is_duplicated = True
break
if not is_duplicated:
lookup[nums[i] + nums[j]].append([i, j])

``````

Check for the other two values which will be added with the values in the lookup dictionary and must return the target value. Don’t forget about the constraints that, a < b < c < d.

Complete Solution:

``````class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums, result, lookup = sorted(nums), [], collections.defaultdict(list)
# print(lookup)
for i in xrange(0, len(nums) - 1):
for j in xrange(i + 1, len(nums)):
is_duplicated = False
for [x, y] in lookup[nums[i] + nums[j]]:
if nums[x] == nums[i]:
is_duplicated = True
break
if not is_duplicated:
lookup[nums[i] + nums[j]].append([i, j])
print(lookup)
ans = {}
for c in xrange(2, len(nums)):
for d in xrange(c+1, len(nums)):
if target - nums[c] - nums[d] in lookup:
for [a, b] in lookup[target - nums[c] - nums[d]]:
if b < c:
quad = [nums[a], nums[b], nums[c], nums[d]]
if quad_hash not in ans:
return result``````