18. 4Sum

【Description】
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]
]

【Idea】

参考2sum的算法，列表排序后，取最左和最右的数，判断两边之和与target的大小，不断向中间夹逼；
Nsum利用递归，从左向右遍历，在i处求nums[i+1:]的(N-1)sum，直至求解2sum，然后返回；
注意设无解时的条件：N<2 or 列表不存在和等于target的解 or len(nums) < N

【Solution】

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        def findNsum(nums, N, result, target, results):
            if len(nums) < N or nums[-1] * N  < target or nums[0] * N  > target or N < 2:
                return 
            if N ==2:
                left, right = 0, len(nums) - 1
                while left < right:
                    if nums[left] + nums[right] == target:
                        results.append(result + [nums[left], nums[right]])
                        left += 1
                        while nums[left] == nums[left-1] and left < right:
                            left +=1
                    elif nums[left] + nums[right] < target:
                        left += 1
                    else:
                        right -= 1             
            else:
                for i in range(len(nums)-N+1):
                    if i==0 or (i > 0 and nums[i] != nums[i-1]):
                        findNsum(nums[i+1:], N-1, result + [nums[i]], target-nums[i], results)
        results = []
        nums.sort()
        findNsum(nums, 4, [], target, results)
        return results