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:
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中表现要比第一种好很多。
原文：http://www.cnblogs.com/zhuifengjingling/p/5218816.html