Question

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [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

\(O(n^3)\). Use double for-loops to capture all possible combinations of first two numbers, and then use the greedy method in 2Sum to find a combination of the remaining two numbers. Thus it is \(O(n^2)\) to run the double for-loop, and \(O(n)\) to find the combination.

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        res = set()

        length = len(nums)
        for i, n in enumerate(nums[:-3]):
            for j in range(i+1, length-2):
                m = nums[j]
                if n + m + nums[j+1] + nums[j+2] <= target and n + m + nums[-1] + nums[-2] >= target:
                    l, r = j + 1, length - 1
                    while l < r:
                        s = n + m + nums[l] + nums[r]
                        if s < target:
                            l += 1
                        elif s > target:
                            r -= 1
                        else:
                            res.add((n, m, nums[l], nums[r]))
                            l += 1
                            r -= 1

        return [list(x) for x in res]