# 18. 4Sum

## Description

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 < n
• a, b, c, and d are 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

## Solutions

Solution 1: Sorting + Double Pointers

We notice that the problem requires us to find non-repeating quadruplets. Therefore, we can first sort the array, which makes it easy to skip duplicate elements.

Next, we enumerate the first two elements of the quadruplet, $nums[i]$ and $nums[j]$, where $i \lt j$. During the enumeration process, we skip duplicate $nums[i]$ and $nums[j]$. Then, we use two pointers $k$ and $l$ to point to the two ends behind $nums[i]$ and $nums[j]$. Let $x = nums[i] + nums[j] + nums[k] + nums[l]$, we compare $x$ with $target$ and perform the following operations:

• If $x \lt target$, then update $k = k + 1$ to get a larger $x$;
• If $x \gt target$, then update $l = l - 1$ to get a smaller $x$;
• Otherwise, it means that a quadruplet $(nums[i], nums[j], nums[k], nums[l])$ is found. Add it to the answer, then we update the pointers $k$ and $l$, and skip all duplicate elements to prevent the answer from containing duplicate quadruplets, and continue to find the next quadruplet.

The time complexity is $O(n^3)$, and the space complexity is $O(\log n)$. Here, $n$ is the length of the array.

• class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
int n = nums.length;
List<List<Integer>> ans = new ArrayList<>();
if (n < 4) {
return ans;
}
Arrays.sort(nums);
for (int i = 0; i < n - 3; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < n - 2; ++j) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int k = j + 1, l = n - 1;
while (k < l) {
long x = (long) nums[i] + nums[j] + nums[k] + nums[l];
if (x < target) {
++k;
} else if (x > target) {
--l;
} else {
while (k < l && nums[k] == nums[k - 1]) {
++k;
}
while (k < l && nums[l] == nums[l + 1]) {
--l;
}
}
}
}
}
return ans;
}
}

//

// general solution, k-sum
// https://leetcode.com/problems/4sum/solution/
// below kSum() divide-and-conquer idea is good, but not passing Online-Judge
class Solution {

public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
return kSum(nums, target, 0, 4);
}

public List<List<Integer>> kSum(int[] nums, int target, int start, int k) {
List<List<Integer>> res = new ArrayList<>();
if (start == nums.length || nums[start] * k > target || target > nums[nums.length - 1] * k)
return res;
if (k == 2)
return twoSum(nums, target, start);
for (int i = start; i < nums.length; ++i)
if (i == start || nums[i - 1] != nums[i]) // 'i == start' is key, since it could be in a following recurion of [1,1,1] where start is 3rd '1'
for (List<Integer> set : kSum(nums, target - nums[i], i + 1, k - 1)) {
}
return res;
}

public List<List<Integer>> twoSum(int[] nums, int target, int start) {
List<List<Integer>> res = new ArrayList<>();
int lo = start, hi = nums.length - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
if (sum < target || (lo > start && nums[lo] == nums[lo - 1]))
++lo;
else if (sum > target || (hi < nums.length - 1 && nums[hi] == nums[hi + 1]))
--hi;
else
}
return res;
}
}

public class Four_Sum {

public static void main(String[] args) {
Four_Sum out = new Four_Sum();
Solution s = out.new Solution();
//		SolutionForLoop s= out.new SolutionForLoop();

List<List<Integer>> result = s.fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0);

for (List<Integer> each : result) {
String one = "";

for (int e : each) {
one = one + " " + e;
}

System.out.println(one);
}
}

// time: O(NlogN)
// space: O(1)
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {

List<List<Integer>> list = new ArrayList<>();

if (nums.length < 4) {
return list;
}

Arrays.sort(nums);

// improved based on 3-sum
int layer4 = 0;
while (layer4 < nums.length) {

// @note: below is causing me trouble when convert for to while
// 			in while, here "layer4" is never updated for case like {0,0,0,0}
// if(layer4 > 0 && nums[layer4] == nums[layer4 - 1]) continue;
if (layer4 > 0 && nums[layer4] == nums[layer4 - 1]) {
layer4++;
}

// hold one pointer, other two pointer moving
int ancher = layer4 + 1;
while (ancher < nums.length) {

int i = ancher + 1;
int j = nums.length - 1;

while (i < j) {

int sum = nums[layer4] + nums[ancher] + nums[i] + nums[j];

if (sum == target) {

// @note: Arrays.asList()

// @note: dont forget move pointers
i++;
j--;

// @note: optimization. above i,j is updated already, compare with previous position
while (i < j && nums[i] == nums[i - 1]) {
i++;
}
while (j > i && nums[j] == nums[j + 1]) {
j--;
}

} else if (sum < target) {
i++;

// @note: same here, possibly updated already, note i-1 or i+1
while (i < j && nums[i] == nums[i - 1]) {
i++;
}

} else {
j--;

// @note: same here, possibly updated already, note i-1 or i+1
while (j > i && j + 1 < nums.length && nums[j] == nums[j + 1]) {
j--;
}

}
}

ancher++;

// optimize for 2nd pointer
while (ancher > layer4 && ancher < nums.length && nums[ancher] == nums[ancher - 1]) {
ancher++;
}

}

layer4++;

// optimize for 2nd pointer
while (layer4 < nums.length && nums[layer4] == nums[layer4 - 1]) {
layer4++;
}
}

return list;
}
}
}


• class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
vector<vector<int>> ans;
if (n < 4) {
return ans;
}
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 3; ++i) {
if (i && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < n - 2; ++j) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int k = j + 1, l = n - 1;
while (k < l) {
long long x = (long long) nums[i] + nums[j] + nums[k] + nums[l];
if (x < target) {
++k;
} else if (x > target) {
--l;
} else {
ans.push_back({nums[i], nums[j], nums[k++], nums[l--]});
while (k < l && nums[k] == nums[k - 1]) {
++k;
}
while (k < l && nums[l] == nums[l + 1]) {
--l;
}
}
}
}
}
return ans;
}
};

• # k-sum
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
return self.kSum(nums, target, 0, 4)

def kSum(self, nums: List[int], target: int, start: int, k: int) -> List[List[int]]:
res = []
if start == len(nums) or nums[start] * k > target or target > nums[-1] * k:
return res
if k == 2:
return self.twoSum(nums, target, start)
for i in range(start, len(nums)):
if i == start or nums[i - 1] != nums[i]:
# here is a hidden matching target==0
# if not matching target, then kSum() will return empty list
for sset in self.kSum(nums, target - nums[i], i + 1, k - 1):
# if kSum(k-1) return empty, it will not execute this line
res.append([ nums[i] ] + sset) # put nums[i] in a list
return res

def twoSum(self, nums: List[int], target: int, start: int) -> List[List[int]]:
res = []
lo, hi = start, len(nums) - 1
while lo < hi:
s = nums[lo] + nums[hi]
if s < target or (lo > start and nums[lo] == nums[lo - 1]):
lo += 1
elif s > target or (hi < len(nums) - 1 and nums[hi] == nums[hi + 1]):
hi -= 1
else:
res.append([nums[lo], nums[hi]])
# continue searching, could be multiple answers
lo += 1
hi -= 1
return res

#########

class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n = len(nums)
ans = []
if n < 4:
return ans
nums.sort()
for i in range(n - 3):
if i and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
k, l = j + 1, n - 1
while k < l:
x = nums[i] + nums[j] + nums[k] + nums[l]
if x < target:
k += 1
elif x > target:
l -= 1
else:
ans.append([nums[i], nums[j], nums[k], nums[l]])
k, l = k + 1, l - 1
while k < l and nums[k] == nums[k - 1]:
k += 1
while k < l and nums[l] == nums[l + 1]:
l -= 1
return ans


• func fourSum(nums []int, target int) (ans [][]int) {
n := len(nums)
if n < 4 {
return
}
sort.Ints(nums)
for i := 0; i < n-3; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
for j := i + 1; j < n-2; j++ {
if j > i+1 && nums[j] == nums[j-1] {
continue
}
k, l := j+1, n-1
for k < l {
x := nums[i] + nums[j] + nums[k] + nums[l]
if x < target {
k++
} else if x > target {
l--
} else {
ans = append(ans, []int{nums[i], nums[j], nums[k], nums[l]})
k++
l--
for k < l && nums[k] == nums[k-1] {
k++
}
for k < l && nums[l] == nums[l+1] {
l--
}
}
}
}
}
return
}

• function fourSum(nums: number[], target: number): number[][] {
const n = nums.length;
const ans: number[][] = [];
if (n < 4) {
return ans;
}
nums.sort((a, b) => a - b);
for (let i = 0; i < n - 3; ++i) {
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
for (let j = i + 1; j < n - 2; ++j) {
if (j > i + 1 && nums[j] === nums[j - 1]) {
continue;
}
let [k, l] = [j + 1, n - 1];
while (k < l) {
const x = nums[i] + nums[j] + nums[k] + nums[l];
if (x < target) {
++k;
} else if (x > target) {
--l;
} else {
ans.push([nums[i], nums[j], nums[k++], nums[l--]]);
while (k < l && nums[k] === nums[k - 1]) {
++k;
}
while (k < l && nums[l] === nums[l + 1]) {
--l;
}
}
}
}
}
return ans;
}


• /**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function (nums, target) {
const n = nums.length;
const ans = [];
if (n < 4) {
return ans;
}
nums.sort((a, b) => a - b);
for (let i = 0; i < n - 3; ++i) {
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
for (let j = i + 1; j < n - 2; ++j) {
if (j > i + 1 && nums[j] === nums[j - 1]) {
continue;
}
let [k, l] = [j + 1, n - 1];
while (k < l) {
const x = nums[i] + nums[j] + nums[k] + nums[l];
if (x < target) {
++k;
} else if (x > target) {
--l;
} else {
ans.push([nums[i], nums[j], nums[k++], nums[l--]]);
while (k < l && nums[k] === nums[k - 1]) {
++k;
}
while (k < l && nums[l] === nums[l + 1]) {
--l;
}
}
}
}
}
return ans;
};


• public class Solution {
public IList<IList<int>> FourSum(int[] nums, int target) {
int n = nums.Length;
var ans = new List<IList<int>>();
if (n < 4) {
return ans;
}
Array.Sort(nums);
for (int i = 0; i < n - 3; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < n - 2; ++j) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int k = j + 1, l = n - 1;
while (k < l) {
long x = (long) nums[i] + nums[j] + nums[k] + nums[l];
if (x < target) {
++k;
} else if (x > target) {
--l;
} else {
ans.Add(new List<int> {nums[i], nums[j], nums[k++], nums[l--]});
while (k < l && nums[k] == nums[k - 1]) {
++k;
}
while (k < l && nums[l] == nums[l + 1]) {
--l;
}
}
}
}
}
return ans;
}
}

• class Solution {
/**
* @param int[] $nums * @param int$target
* @return int[][]
*/

function fourSum($nums,$target) {
$result = [];$n = count($nums); sort($nums);

for ($i = 0;$i < $n - 3;$i++) {
if ($i > 0 &&$nums[$i] ===$nums[$i - 1]) { continue; } for ($j = $i + 1;$j < $n - 2;$j++) {
if ($j >$i + 1 && $nums[$j] === $nums[$j - 1]) {
continue;
}

$left =$j + 1;
$right =$n - 1;

while ($left <$right) {
$sum =$nums[$i] +$nums[$j] +$nums[$left] +$nums[$right]; if ($sum === $target) {$result[] = [$nums[$i], $nums[$j], $nums[$left], $nums[$right]];

while ($left <$right && $nums[$left] === $nums[$left + 1]) {
$left++; } while ($left < $right &&$nums[$right] ===$nums[$right - 1]) {$right--;
}

$left++;$right--;
} elseif ($sum <$target) {
$left++; } else {$right--;
}
}
}
}
return \$result;
}
}