LeetCode #18 2018-07-28

18. 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/description/

这道题的核心思想是实现一个2-sum，并利用递归将一个N-sum的问题化简为2-sum问题。由于我们已将数组排序，所以可以利用这个性质部分优化我们的代码。
代码如下：

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def findNSum(nums, N, target, result, results):
            if len(nums) < N or N < 2 or nums[0] * N > target or nums[-1] * N < target:
                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
                        right -= 1
                        while(left < right and nums[left] == nums[left - 1]):
                            left += 1
                        while(left < right and nums[right] == nums[right + 1]):
                            right -= 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 (nums[i - 1] != nums[i]):
                        findNSum(nums[1 + i:], N - 1, target - nums[i], result + [nums[i]], results)

        results = []
        findNSum(sorted(nums), 4, target, [], results)

        return results