Given an array S of n integers, are there elements a, b, c, and d in S 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.

For example, given array S = [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]
]

Solution1

利用3sum的算法，完善4sum。
难处还是在于去重的细节做法

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = []
        nums.sort()
        for i in range(len(nums) - 3):
            if i >= 1 and nums[i] == nums[i - 1]: continue
            for j in range(i + 1, len(nums) - 2):
                if j >= 2 and i != j - 1 and nums[j] == nums[j - 1]: continue
                k, l = j + 1, len(nums)-1
                while(k < l):
                    #print i, j, k, l
                    #print nums, nums[i], nums[j], nums[k], nums[l]
                    sum = nums[i] + nums[j] + nums[k] + nums[l]
                    if sum > target:
                        l -= 1
                    elif sum < target:
                        k += 1
                    else:
                        result.append([nums[i], nums[j], nums[k], nums[l]])
                        while(k < l) and nums[k] == nums[k + 1]:
                            k += 1
                        while(k < l) and nums[l] == nums[l - 1]:
                            l -= 1
                        l -= 1
                        k += 1

        return result

Solution2

从2sum, 3sum的做法朝后看，使用递归完成Nsum。

def fourSum(self, nums, target):
    def findNsum(nums, target, N, result, results):
        if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N:  # early termination
            return
        if N == 2: # two pointers solve sorted 2-sum problem
            l,r = 0,len(nums)-1
            while l < r:
                s = nums[l] + nums[r]
                if s == target:
                    results.append(result + [nums[l], nums[r]])
                    l += 1
                    while l < r and nums[l] == nums[l-1]:
                        l += 1
                elif s < target:
                    l += 1
                else:
                    r -= 1
        else: # recursively reduce N
            for i in range(len(nums)-N+1):
                if i == 0 or (i > 0 and nums[i-1] != nums[i]):
                    findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)

    results = []
    findNsum(sorted(nums), target, 4, [], results)
    return results

反思

• 相同的问题，不停地出现，作为懒惰的程序员，需要寻找规律，给出一个general solution