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)

# medium: http://lintcode.com/zh-cn/problem/4sum/