# 4Sum

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

Note:

The solution set must not contain duplicate quadruplets.

Example:

`Given array nums = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [       [-1,  0, 0, 1],       [-2, -1, 1, 2],       [-2,  0, 0, 2] ]`
```class Solution:
def fourSum(self, nums, target):

def findNsum(nums, target, N, result, results):
# early termination
if len(nums) < N or N < 2 or target < nums * N or target > nums[-1] * N:
return

# two pointers solve sorted 2-sum problem
if N == 2:
l = 0
r = len(nums) - 1

while l < r:
s = nums[l] + nums[r]
if s == target:
results.append(result + [nums[l], nums[r]])
l += 1
while l < r and nums[l] == nums[l - 1]:
l += 1
elif s < target:
l += 1
else:
r -= 1
while l < r and nums[r] == nums[r + 1]:
r -= 1

# recursively reduce N
else:
for i in range(len(nums) - N + 1):
if i == 0 or (i > 0 and nums[i - 1] != nums[i]):
findNsum(nums[i + 1:], target - nums[i], N - 1, result + [nums[i]], results)

results = []
findNsum(sorted(nums), target, 4, [], results)
return results```