# [Leetcode]18. 4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in numssuch 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] ]

I know, first [Leetcode]1. Two Sum, then [Leetcode]15. 3Sum, now 4Sum, will there be 5Sum, 6Sum etc.? Well, now we can work on a generalized approach to solve N Sum problem!

#### Logic

Let’s backtrack a little bit:

• 2Sum: we applied two pointers to find a+b=target.
• 3Sum: we fixed one number num at a time and applied two pointers to the remaining looking for a+b=target-num – that’s like 2Sum!!!

And now:

• 4Sum, we could fix one number a at a time and search through the remaining for b,c, and d such that b+c+d=target-a – that’s like 3Sum!!!

Following this intuition, N Sum problem is like a Matryoshka doll, and we can literally reduce N Sum to N-1 Sum, to N-2 Sum, and finally to 2 Sum, which could be solved with two pointers.

#### Code

class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
ans = []
def n_sum(n,l,r,t,cur):
"""solves N sum problem

Args:
n (int): defines N
l (int): starting index for the subarray
r (int): ending index for the subarray
t (int): the target for the N sum problem
cur (list): recording the combinations
"""
nonlocal ans
# if 2 Sum, apply two pointers
if n == 2:
ret = []
while l < r:
if nums[l] + nums[r] > t:
r -= 1
elif nums[l] + nums[r] < t:
l += 1
else:
ret.append(cur+[nums[l],nums[r]])
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1
r -= 1
ans += ret
else: # reduce the problem to n-1 Sum
i = l
while i < r+1:
if nums[i]*n > t or nums[-1]*n < t:
break
n_sum(n-1,i+1,r,t-nums[i],cur+[nums[i]])
i += 1
while i and i < r+1 and nums[i]==nums[i-1]:
i += 1
n_sum(4,0,len(nums)-1,target,[])
return ans

Subscribe
Notify of