# 18. 4Sum

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

Approach 1: Sorting and then for each number, do 3-sum for the rest of numbers.

Approach 2: use a hash table to stores pairs, then use 2-level loops to find another pair. Use a set to dedup.

# Code (Python)

Approach 1:

    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # idea: build everything upon 2sum -- https://leetcode.com/problems/4sum/discuss/8545/Python-140ms-beats-100-and-works-for-N-sum-(Ngreater2)
        nums.sort()
        return self._n_sum(4, nums, target)
    
    def _n_sum(self, n, nums, target): # can also pass the start and end indices instead of slicing
        result = []
        if n == 2:
            l, r = 0, len(nums) - 1
            while l < r:
                if nums[l] + nums[r] == target:
                    result.append([nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1
                    while l < r and nums[r] == nums[r + 1]:
                        r -= 1
                elif nums[l] + nums[r] < target:
                    l += 1
                else:
                    r -= 1
        else:
            for i in range(len(nums) - n + 1):
                if i > 0 and nums[i] == nums[i - 1]:
                    continue
                result.extend([[nums[i]] + _ for _ in self._n_sum(n - 1, nums[i + 1:], target - nums[i])])
        
        return result

Approach 2:

    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # O(n^2): hash table stores a pair, then use 2-level loops to find another pair
        # http://chaoren.is-programmer.com/posts/45308.html
        if not nums or len(nums) < 4:
            return []
        nums.sort()
        result = set()
        table = collections.defaultdict(list)
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                table[nums[i] + nums[j]].append((i, j))
        for i in range(len(nums)):
            for j in range(i + 1, len(nums) - 2):
                for pair in table[target - nums[i] - nums[j]]:
                    if pair[0] > j:
                        result.add((nums[i], nums[j], nums[pair[0]], nums[pair[1]]))
        return list(result)

# Code (C++)

Approach 1:

class Solution {
private:
    // Two pointers.
    vector<vector<int>> twoSum(vector<int>& nums, int head, int tail, int target) {
        vector<vector<int>> res;
        int i = head;
        int j = tail;
        while (i < j)
        {
            if (i > head && nums[i] == nums[i-1])
                i++;
            else if (j < nums.size() - 1 && nums[j] == nums[j+1])
                j--;
            else
            {
                int sum = nums[i] + nums[j];
                if (sum < target)
                    i++;
                else if (sum > target)
                    j--;
                else
                {
                    vector<int> pair = vector<int>();
                    pair.push_back(nums[i]);
                    pair.push_back(nums[j]);
                    res.push_back(pair);
                    i++;
                    j--;
                }
            }
        }
        return res;
    }
    vector<vector<int>> threeSum(vector<int>& nums, int head, int tail, int target) {
        vector<vector<int>> res;
        std::sort(nums.begin(), nums.end());
        for (int i = head; i <= tail; ++i)
        {
            if (i > head && nums[i] == nums[i-1])
                continue;
            vector<vector<int>> pairs =
                twoSum(nums, i + 1, nums.size() - 1, target - nums[i]);
            for (auto it = pairs.begin(); it != pairs.end(); ++it)
            {
                it->push_back(nums[i]);
                res.push_back(*it);
            }
        }
        return res;
    }
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        std::sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++i)
        {
            if (i > 0 && nums[i] == nums[i-1])
                continue;
            vector<vector<int>> trios =
                threeSum(nums, i + 1, nums.size() - 1, target - nums[i]);
            for (auto it = trios.begin(); it != trios.end(); ++it)
            {
                it->push_back(nums[i]);
                res.push_back(*it);
            }
        }
        return res;
    }
};