public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
if (nums.length < 4) {
return res;
}
Arrays.sort(nums);
if (4 * nums[nums.length - 1] < target) {
return res;
}
int max3Sum = 3 * nums[nums.length - 1];
int lastsize = res.size();
for (int i = 0; i < nums.length - 3; i++) {
if (i > 0 && nums[i - 1] == nums[i]) {
continue;
}
if (nums[i] * 4 > target) {
break;
}
if (nums[i] + max3Sum < target) {
continue;
}
threeSum(res, nums, target - nums[i], i + 1);
while (lastsize < res.size()) {
res.get(lastsize).add(nums[i]);
lastsize++;
}
}
return res;
}
private void threeSum(List<List<Integer>> res, int[] nums, int target, int lo) {
int max2Sum = 2 * nums[nums.length - 1];
int lastsize = res.size();
for (int i = lo; i < nums.length - 2; i++) {
if (i > lo && nums[i] == nums[i - 1]) {
continue;
}
if (nums[i] * 3 > target) {
break;
}
if (nums[i] + max2Sum < target) {
continue;
}
twoSum(res, nums, target - nums[i], i + 1);
while (lastsize < res.size()) {
res.get(lastsize).add(nums[i]);
lastsize++;
}
}
}
private void twoSum(List<List<Integer>> res, int[] nums, int target, int lo) {
int hi = nums.length - 1;
while (lo < hi) {
if (2 * nums[lo] > target || 2 * nums[hi] < target) {
break;
}
int sum = nums[lo] + nums[hi];
if (sum == target) {
List<Integer> tuple = new ArrayList<>();
tuple.add(nums[lo]);
tuple.add(nums[hi]);
res.add(tuple);
lo++;
hi--;
while (lo < hi && nums[lo - 1] == nums[lo]) {
lo++;
}
while (lo < hi && nums[hi + 1] == nums[hi]) {
hi--;
}
} else if (sum > target) {
hi--;
} else {
lo++;
}
}
}