4Sum

Question

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

Tags

• Array
• Hash Map

Thought

The solution is very similar to the Two Sum problem:

1. Use the sum of two elements in the array nums as the key in the dictionary.
2. Use the set to avoid duplication in the result array.

Code

class Solution(object):
    def fourSum(self, nums, target):
        """
        Starts from the 3Sum approach
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        # http://www.cnblogs.com/zuoyuan/p/3699384.html
        sumDict = {}
        result = set()
        for i in xrange(len(nums)):
            for j in xrange(i + 1, len(nums)):
                tmpSum = nums[i] + nums[j]
                if tmpSum not in sumDict:
                    sumDict[tmpSum] = [(i, j)]
                else:
                    sumDict[tmpSum].append((i, j))
                if target - tmpSum in sumDict:
                    for item in sumDict[target - tmpSum]:
                        if i in item or j in item:
                            continue
                        tmp = sorted([nums[i], nums[j], nums[item[0]], nums[item[1]]])
                        result.add(tuple(tmp))
        ans = []
        for item in result:
            ans += [list(item)]
        return ans