Algorithm
Problem Name: 18. 4Sum
Problem Link: https://leetcode.com/problems/4sum/
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < na,b,c, anddare distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]]
Constraints:
1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector < vector<int>>res;
vector<int>path;
DFS(res, nums, 0, target, 0, 0, path);
return res;
}
void DFS(vector < vector<int>>& res, vector<int>& nums, int pos, int target, int count, int sum, vector<int>& path){
if(count == 4){
if(sum == target) res.push_back(path);
return;
}
for(int i = pos; i < nums.size(); i++){
if(i != pos && nums[i] == nums[i - 1]) continue;
if(sum + nums[i] + (3 - count) * nums[nums.size() - 1] < target) continue;
if(sum + (4 - count>* nums[i] > target) break;
path.push_back(nums[i]);
DFS(res, nums, i + 1, target, count + 1, sum + nums[i], path);
path.pop_back();
}
}
};
Input
nums = [1,0,-1,0,-2,2], target = 0
Output
[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List();
if (start == nums.length) {
return result;
}
long averageValue = target / k;
if (nums[start] > averageValue || averageValue > nums[nums.length - 1]) {
return result;
}
if (k == 2) {
return twoSum(nums, target, start);
}
for (int i = start; i < nums.length; ++i) {
if (i == start || nums[i - 1] != nums[i]) {
for (List subset : kSum(nums, target - nums[i], i + 1, k - 1)) {
result.add(new ArrayList<>(Arrays.asList(nums[i])));
result.get(result.size() - 1).addAll(subset);
}
}
}
return result;
}
public List < List();
int low = start;
int high = nums.length - 1;
while (low < high) {
int currSum = nums[low] + nums[high];
if (currSum < target || (low > start && nums[low] == nums[low - 1])) {
++low;
} else if (currSum > target || (high < nums.length - 1 && nums[high] == nums[high + 1])) {
--high;
} else {
result.add(Arrays.asList(nums[low++], nums[high--]));
}
}
return result;
}
}
Input
nums = [2,2,2,2,2], target = 8
Output
[[2,2,2,2]]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const fourSum = function (nums, target) {
nums.sort((a, b) => a - b)
const results = []
kSum(nums, target, 4, 0, [], results)
return results
}
function kSum(nums, target, k, i, acc, results) {
if (nums[i] * k > target || nums[nums.length - 1] * k < target) return
if (k > 2) {
for (let j = i; j < = nums.length - k; j++) {
if (j == i || nums[j] > nums[j - 1])
kSum(nums, target - nums[j], k - 1, j + 1, [...acc, nums[j]], results)
}
} else {
twoSum(nums, target, i, acc, results)
}
}
function twoSum(nums, target, i, acc, results) {
let lo = i
let hi = nums.length - 1
while (lo < hi) {
const sum = nums[lo] + nums[hi]
if (sum == target) {
results.push([...acc, nums[lo], nums[hi]])
while (nums[lo] == nums[lo + 1]) lo++
while (nums[hi] == nums[hi - 1]) hi--
lo++
hi--
} else if (sum < target) {
lo++
} else {
hi--
}
}
}
Input
nums = [2,2,2,2,2], target = 8
Output
[[2,2,2,2]]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def fourSum(self, nums, target):
res, res_set = [], set()
nums.sort()
for i in range(len(nums) - 1):
if i > 0 and nums[i] == nums[i - 1]: continue
for j in range(i + 1, len(nums)):
l, r = j + 1, len(nums) - 1
while l < r:
sm = nums[i] + nums[j] + nums[l] + nums[r]
if sm < target: l += 1
elif sm > target: r -= 1
elif (nums[i], nums[j], nums[l], nums[r]) not in res_set:
res.append([nums[i], nums[j], nums[l], nums[r]]); res_set.add((nums[i], nums[j], nums[l], nums[r]))
else: l, r = l + 1, r - 1
return res
Input
nums = [1,0,-1,0,-2,2], target = 0
Output
[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
#5 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _018_4Sum
{
public IList < IList<int>> FourSum(int[] nums, int target)
{
var results = new List < IList<int>>();
if (nums.Length < 4) { return results; }
Suffle(nums);
Quick3WaySort(nums, 0, nums.Length - 1);
var cache = new Dictionary < int, IList<int>>();
int temp, index1, index2;
for (index1 = 0; index1 < nums.Length - 1; index1++)
{
for (index2 = index1 + 1; index2 < nums.Length; index2++)
{
temp = nums[index1] + nums[index2];
if (!cache.ContainsKey(temp))
{
cache[temp] = new List < int>();
}
cache[temp].Add(index1);
cache[temp].Add(index2);
}
}
IList < int> list1, list2;
foreach (var pair in cache)
{
if (!cache.TryGetValue(target - pair.Key, out list2)) { continue; }
list1 = pair.Value;
for (index1 = 0; index1 < list1.Count; index1 += 2)
{
for (index2 = 0; index2 < list2.Count; index2 += 2)
{
if ((list1[index1 + 1] < list2[index2]) && (list1[index1] != list2[index2] && list1[index1] != list2[index2 + 1]))
{
results.Add(new List<int>() { nums[list1[index1]], nums[list1[index1 + 1]], nums[list2[index2]], nums[list2[index2 + 1]] });
while (index2 + 2 < list2.Count && nums[list2[index2 + 2]] == nums[list2[index2]])
{
index2 += 2;
}
}
}
while (index1 + 2 < list1.Count && nums[list1[index1 + 3]] == nums[list1[index1 + 1]])
{
index1 += 2;
}
}
}
return results;
}
void Suffle(int[] nums)
{
var random = new Random();
int N = nums.Length;
int r, temp;
for (int i = 0; i < N; i++)
{
r = random.Next(i + 1);
temp = nums[r];
nums[r] = nums[i];
nums[i] = temp;
}
}
void Quick3WaySort(int[] nums, int lo, int hi)
{
if (lo >= hi) { return; }
var lt = lo;
var gt = hi;
var i = lo;
var v = nums[i];
int temp;
while (i < = gt)
{
if (nums[i] > v)
{
temp = nums[i];
nums[i] = nums[gt];
nums[gt--] = temp;
}
else if (nums[i] < v)
{
temp = nums[i];
nums[i] = nums[lt];
nums[lt++] = temp;
}
else { i++; }
}
Quick3WaySort(nums, lo, lt - 1);
Quick3WaySort(nums, gt + 1, hi);
}
}
}
Input
nums = [2,2,2,2,2], target = 8
Output
[[2,2,2,2]]