18_4Sum.py

"""
https://leetcode.com/problems/4sum/

Given an array nums of n integers and an integer target, are there elements a, b, c, 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]
]
"""
"""
https://leetcode.com/problems/4sum/discuss/8545/Python-140ms-beats-100-and-works-for-N-sum-(Ngreater2)
"""
class Solution:
    def fourSum(self, nums: 'List[int]', target: 'int') -> 'List[List[int]]':
        nums.sort()
        results = []
        self.findNsum(nums, target, 4, [], results)
        return results
    def findNsum(self, nums: 'List[int]', target: 'int', N: 'int', result: 'List[int]', results: 'List[int]'):
        if len(nums)<N or N<2:
            return
        #2-sum
        if N==2:
            l, r = 0, len(nums)-1
            while l<r:
                if nums[l]+nums[r] == target:
                    results.append(result+[nums[l], nums[r]])
                    l+=1
                    r-=1
                    while l<r and nums[l]==nums[l-1]:
                        l+=1
                    while l<r and nums[r]==nums[r+1]:
                        r-=1
                elif nums[l]+nums[r] < target:
                    l+=1
                else:
                    r-=1
        #回溯
        else:
            for i in range(len(nums)-N+1):
                if nums[i]*N>target or nums[-1]*N<target:
                    break
                if i==0 or i>0 and nums[i]!=nums[i-1]:
                    self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
        

x = Solution()
print(x.fourSum([1, 0, -1, 0, -2, 2], 0))