18. 4Sum
You are given an integer array nums and an integer target. Find every distinct quadruplet of values [a, b, c, d] that can be formed by picking four different positions of the array such that a + b + c + d == target, and return them as a list of quadruplets.
Two quadruplets count as the same if they contain the same four values (with multiplicity), regardless of which positions produced them — the result must contain no duplicates.
Return the answer in canonical form: each quadruplet sorted in non-decreasing order, and the list of quadruplets sorted in ascending lexicographic order. If no quadruplet works, return an empty list.
Watch the arithmetic: values reach ±10⁹, so intermediate sums overflow 32-bit integers.
Example 1:
Input: nums = [3, -1, 0, 2, 1, -2], target = 2
Output: [[-2, -1, 2, 3], [-2, 0, 1, 3], [-1, 0, 1, 2]]
Explanation: Three distinct value-quadruplets reach 2. Each line is internally sorted and the lines appear in ascending order.
Example 2:
Input: nums = [2, 2, 2, 2, 2], target = 8
Output: [[2, 2, 2, 2]]
Explanation: Five different position choices all produce the same values [2, 2, 2, 2], so it is reported exactly once.
Constraints:
- 1 ≤ nums.length ≤ 200
- -10⁹ ≤ nums[i] ≤ 10⁹
- -10⁹ ≤ target ≤ 10⁹
- Sums of four elements can exceed 32-bit range — use 64-bit arithmetic.
Hints:
This is 3Sum with one more layer: sort first, fix TWO elements with nested loops, and the remainder is a classic pair-sum-to-target search.
On a sorted array, the inner pair search is a left/right pointer squeeze: sum too small → move left up, too big → move right down.
Duplicates are handled by skipping: after fixing or matching a value, advance past every copy of it at that level (i, j, l, and r each skip their own repeats). That both dedupes and keeps the output in sorted order for free.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [3, -1, 0, 2, 1, -2], target = 2
Expected output: [[-2, -1, 2, 3], [-2, 0, 1, 3], [-1, 0, 1, 2]]