# Accepted Java solution

• Another for loop is added to the 3Sum solution and we have this.

public class Solution {
public List<List<Integer>> fourSum(int[] num, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (num.length < 4) {
return result;
}
Arrays.sort(num);

for (int i = 0; i < num.length - 3; i++) {
if (i > 0 && num[i] == num[i - 1]) {
continue;
}
for (int j = num.length - 1; j > i + 2; j--) {
if (j < num.length - 1 && num[j] == num[j + 1]) {
continue;
}
int start = i + 1;
int end = j - 1;
int n = target - num[i] - num[j];
while (start < end) {
if (num[start] + num[end] == n) {
List<Integer> four = new ArrayList<Integer>();
do { start++; } while (start < end && num[start] == num[start - 1]);
do { end--; } while (start < end && num[end] == num[end + 1]);
}
else if (num[start] + num[end] < n) {
do { start++; } while (start < end && num[start] == num[start - 1]);
}
else {
do { end--; } while (start < end && num[end] == num[end + 1]);
}

}
}
}

return result;
}
}

• Same Solution for reference. Can be generalized to k-sum.

public class Solution {
public List<List<Integer>> fourSum(int[] num, int target) {
List<List<Integer>> rslt = new ArrayList<List<Integer>>();
Arrays.sort(num);
for(int i = 0;i < num.length-3;i++){
if(i==0 || i> 0 && num[i]!=num[i-1]){
for(int j = i+1;j < num.length-2;j++){
if(j==i+1 || j > i+1 && num[j]!= num[j-1]){
int rest = target - num[i] - num[j];
int low = j+1, high = num.length-1;
while(low < high){
int sum = num[low] + num[high];
if(sum == rest){
List<Integer> list = new ArrayList<Integer>();
while(high > low && num[high] == num[--high]);
while(high > low && num[low] == num[++low]);
}
else if(sum > rest)
high--;
else
low++;

}
}
}
}
}
return rslt;
}
}

• My algorithm is similar to the original author, but I use HashSet to check for duplicates. Thus, it is very to understand.

public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<List<Integer>>();
// set for checking duplicate quadruplet
Set<List<Integer>> preResult = new HashSet<List<Integer>>();
if (nums.length < 4) return result;
// the two pointers
int low = 0, high = 0;

for (int i = 0; i < nums.length - 3; i++) {
for (int j = i+1; j < nums.length - 2; j++) {
low = j+1;
high = nums.length - 1;
// while the two pointers do not meet
while (low < high) {
if (nums[i]+nums[j]+nums[low]+nums[high] == target) {
List<Integer> list = new ArrayList<Integer>();
// add the solution to the set first
// check for the next combination
low++;
high--;
}
else if (nums[i]+nums[j]+nums[low]+nums[high] > target) {
high--;
}
else {
low++;
}
}
}
}
// copy the elements in the set into the list for final answer
for (List<Integer> ls:preResult) {