4sum.py

# -*- coding: utf-8 -*-

class Solution:
 """
 @param numbersbers : Give an array numbersbersbers of n integer
 @param target : you need to find four elements that's sum of target
 @return : Find all unique quadruplets in the array which gives the sum of 
 zero.
 """
 def fourSum(self ,numbers, target):
 # write your code here
 self.ret = []
 self.numbers = numbers
 self.target = target
 self.numbers.sort() # 排序为了方便后面去重
 self.kSum(0, [], 0, 4)
 return self.ret

 def kSum(self, start, data, _sum, k):
 if k == 0:
 if _sum == self.target:
 self.ret.append(data[:])
 elif start < len(self.numbers):
 data.append(self.numbers[start])
 self.kSum(start + 1, data, _sum + self.numbers[start], k - 1)
 data.pop()
 j = start + 1 # 去重不要忘记
 while (j < len(self.numbers)) and (self.numbers[j] == self.numbers[start]):
 j += 1
 self.kSum(j, data, _sum, k)