[Leetcode]18. 4Sum

Given an array nums of n integers and an integer target, are there elements abc, 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.

Russian Dolls – The History of Russian Matryoshka Nesting Dolls

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
guest
0 Comments
Inline Feedbacks
View all comments