# 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;
}
};