# Question

Formatted question description: https://leetcode.ca/all/18.html

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:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
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)

@tag-array



# Algorithm

Sort the original array, and then start traversing the sorted array. Note that the traversal is not to the last stop, but to the third from the bottom. Here you can do a pruning optimization first, that is, break when traversing to a positive number, why, because the array is now ordered, if the first number to be fixed is a positive number, then the following numbers

If they are all positive numbers, the sum will never be zero. Then add the process of skipping if repeated. The processing method is to start with the second number.

If it is equal to the previous number, skip it because you don’t want to fix the same number twice. For the traversed number, subtract the fix number from 0 to get a target, and then only need to find the sum of the two numbers is equal to the target.

Use two pointers to point to the first and last two numbers of the array starting after the fix number. If the sum of the two numbers happens to be the target, then the two numbers and the fix number are stored in the result together. Then is to skip the step of repeating numbers. Both pointers need to detect repeated numbers. If the sum of the two numbers is less than the target, move the pointer i on the left one bit to the right to increase the number pointed to. In the same way, if the sum of the two numbers is greater than the target, move the pointer j on the right to the left to reduce the number pointed to.

# Code

Java

// general solution, k-sum
// https://leetcode.com/problems/4sum/solution/
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