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.

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)

Solution

the most important thing for 2sum, 3sum , 4sum,

the second loop start with the current first loop first index: j = i + 1 , the first item is i + 1

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
        numbers.sort()
        n = len(numbers)
        res = []
        for i in range(n - 3):
            if i > 0 and numbers[i] == numbers[i - 1]:
                continue
            for j in range(i + 1, n - 2):
                total = target - numbers[i] - numbers[j]
                if j != i + 1 and numbers[j] == numbers[j - 1]:
                    continue
                left, right = j + 1, n - 1
                while left < right:
                    if numbers[left] + numbers[right] == total:
                        res.append([numbers[i], numbers[j], numbers[left], numbers[right]])
                        left += 1
                        right -= 1
                        while left < right and numbers[left - 1] == numbers[left]:
                            left += 1
                        while left < right and numbers[right + 1] == numbers[right]:
                            right -= 1
                    elif numbers[left] + numbers[right] < total:
                        left += 1
                    else:
                        right -= 1
        return res