15. 3Sum
You are given an integer array nums. Find every distinct triplet of values that sums to zero, using three different positions of the array (values may repeat, positions may not).
Return the triplets in a canonical form so the answer is unique: inside each triplet the three numbers are in non-decreasing order, the triplets themselves are listed in ascending lexicographic order (compare first numbers, then second, then third), and no triplet of values appears more than once. If nothing sums to zero, return an empty list — the program then prints nothing.
Example 1:
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation: Two value-triplets reach zero: (-1) + (-1) + 2 and (-1) + 0 + 1. Each is written smallest-first, and (-1, -1, 2) precedes (-1, 0, 1) because -1 < 0 in the second position. The pair of -1s comes from two different positions, which is allowed.
Example 2:
Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]
Explanation: The only triplet uses all three zeros: 0 + 0 + 0 = 0. It is reported once.
Constraints:
- 3 ≤ nums.length ≤ 3000
- -10⁵ ≤ nums[i] ≤ 10⁵
Hints:
Sort the array first. Sorting makes equal values adjacent (easy to skip duplicates) and produces the required canonical order as a side effect.
After sorting, fix the smallest member nums[i]. What remains is Two Sum with target -nums[i] on the sorted suffix to the right of i — solvable with two pointers converging from both ends.
Deduplicate at every level: skip a repeated nums[i], and after recording a hit, advance both pointers past any copies of the values they were on.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [-1, 0, 1, 2, -1, -4]
Expected output: [[-1, -1, 2], [-1, 0, 1]]