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: The solution set must not contain duplicate quadruplets.

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]
]

Subscribe to see which companies asked this question


import itertools
import collections
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        ans = []
        cache = collections.defaultdict(list)
        for k,v in enumerate(nums):
            cache[v].append(k)
        explored = set()
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                for k in range(j+1,len(nums)):
                    remain = target -(nums[i]+nums[j]+nums[k])
                    if remain not in cache:
                        continue
                    else:
                        idxs = cache[remain] 
                    if any(t in explored for t in itertools.permutations((nums[i],nums[j],nums[k],remain))):
                        continue
                    for idx in idxs:
                        if idx==i or idx == j or idx == k:
                            continue
                        ans.append([nums[i],nums[j],nums[k],remain])
                        [explored.add(t) for t in itertools.permutations((nums[i],nums[j],nums[k],remain))]
                        break
        return ans

O(n*n*n)