Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

Example:

1 2 3 4 5 6 7 8 9 10 11

Given arraynums= [1, 0, -1, 0, -2, 2], andtarget=0.

A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

public List<List<Integer>> fourSum(int[] nums, int target) { intn= nums.length; // sorting Arrays.sort(nums); // fourSum List<List<Integer>> result = newArrayList<>(); for (inti=0; i < n; ++i) { if (i > 0 && nums[i - 1] == nums[i]) continue; threeSum(nums, i + 1, n - 1, target - nums[i], result); } return result; } privatevoidthreeSum(int[] nums, int lo, int hi, int target, List<List<Integer>> result) { intn= nums.length; intsubLen= hi - lo + 1; for (inti= lo; i <= hi; ++i) { if (i > lo && nums[i] == nums[i - 1]) continue; // skip same result // two pointers intj= i + 1, k = hi; intt= target - nums[i]; while (j < k) { // each element is only used once if (nums[j] + nums[k] < t) { ++j; } elseif (nums[j] + nums[k] > t) { --k; } else { // equal result.add(Arrays.asList(nums[lo - 1], nums[i], nums[j], nums[k])); ++j; --k; while (j < k && nums[j] == nums[j - 1]) j++; // skip same result while (j < k && nums[k] == nums[k + 1]) k--; // skip same result } } } }