18. 4Sum

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:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• 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)

AC代码：

class Solution(object):
    def fourSum(self, nums, target):
        ret_list = []
        nums.sort()
        for i in xrange(len(nums) - 3):
            if i > 0 and nums[i] == nums[i - 1]: continue
            for j in xrange(i + 1, len(nums) - 2):
                if j > i + 1 and nums[j] == nums[j - 1]: continue
                m, n = j + 1, len(nums) - 1
                while m < n:
                    s = nums[i] + nums[j] + nums[m] + nums[n]
                    if s > target:
                        n -= 1
                    elif s < target:
                        m += 1
                    else:
                        ret_list.append([nums[i], nums[j], nums[m], nums[n]])
                        while m < n and nums[m] == nums[m + 1]:
                            m += 1
                        while m < n and nums[n] == nums[n - 1]:
                            n -= 1
                        m += 1; n -= 1
        return ret_list

一开始思路是和3Sum一样，所以直接在外面套了一层循环。

这个代码有两个缺点：

1.没有跳过一些明显不合法的情况，比如排序后第一个数字乘以4已经比目标数字高了，这种情况下肯定找不到想到的组合，应该直接跳过。

2.写的不够通用，考虑到以后万一有个5Sum,6Sum……，本代码又要重构。

所以写了一个支持任意数目组合的通用代码，并且考虑了明显不符合的情况，提高效率。

class Solution(object):
    def fourSum(self, nums, target):
        def n_sum(nums, target, n, temp_result, ret_list):
            # skip unnecessary calculate
            if len(nums) < n or n < 2 or target < n*nums[0] or target > n*nums[-1]:
                return
            # almost exactly the same with Two Sum
            if n == 2:
                i, j = 0, len(nums) - 1
                while i < j:
                    s = nums[i] + nums[j]
                    if s > target:
                        j -= 1
                    elif s < target:
                        i += 1
                    else:
                        ret_list.append(temp_result + [nums[i], nums[j]])
                        # remove duplicates
                        while i < j and nums[i] == nums[i + 1]:
                            i += 1
                        while i < j and nums[j] == nums[j - 1]:
                            j -= 1
                        i += 1; j -= 1
            else:
                for i in xrange(len(nums) - n + 1):
                    if i > 0 and nums[i] == nums[i - 1]: continue
                    n_sum(nums[i+1:], target - nums[i], n - 1, temp_result + [nums[i]], ret_list)

        ret_list = []
        n_sum(sorted(nums), target, 4, [], ret_list)
        return ret_list

因为去除掉了一些不必要的计算，本代码在Leetcode中表现要比第一种好很多。