18.md

18 4Sum

Description

link

---

General Type

NSUM Problem

---

Solution

• Make sure the list is sorted

• define two - sum and remove duplicates

• devided problem to sub_problem of N - 1 Sum

---

Code

Complexity T : O(n^(N - 1)log(n))

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums = sorted(nums)
        return self.NSum(nums, target, 4)
        
    def NSum(self, nums, target, N):
        result = []
        if len(nums) < N or N < 2: return result
        
        if nums[0] * N > target or nums[-1] * N < target:
            return result
        
        if N == 2:
            l, r = 0, len(nums)-1
            while(l < r):
                if nums[l] + nums[r] == target:
                    result.append([nums[l],nums[r]])
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l - 1]: # remove duplicates
                        l += 1
                    while r > l and nums[r] == nums[r + 1]: # remove duplicates
                        r -= 1
                elif nums[l] + nums[r] < target:
                    l += 1
                else: r -= 1
            return result
        else:
            for i in range(len(nums) - N + 1):
                if i != 0 and nums[i] == nums[i - 1]:continue # remove duplicates
                subResult = self.NSum(nums[i + 1:], target - nums[i], N - 1)
                for li in subResult:
                    result.append([nums[i]] + li)
                    
        return result