3Sum

You get an array of integers nums.

Return every triplet of numbers that adds up to 0. The three numbers must come from three different positions.

List each triplet of values once. Two triplets with the same three values count as one, even if they come from different positions.

Write each triplet from its smallest value to its largest. Then list the triplets from smallest to largest. Compare their first values, then their second, then their third.

If you sort nums first and collect the triplets from left to right, they come out in this order.

Example 1:

Input: nums = [3,-2,-1,1,-2,4]
Output: [[-2,-2,4],[-2,-1,3]]
Explanation:
(-2) + (-2) + 4 = 0 uses both -2s (positions 1 and 4).
(-2) + (-1) + 3 = 0 works with either -2. It is listed once.
Both triplets start with -2.
Their second values are -2 and -1.
Since -2 is smaller, the triplet with both -2s comes first.

Example 2:

Input: nums = [5,-1,2,7]
Output: []
Explanation: No three of these numbers add up to 0.

Example 3:

Input: nums = [1,-1,0,1,-1,0]
Output: [[-1,0,1]]
Explanation: Many choices of positions give (-1) + 0 + 1 = 0.
They all use the same values, so the triplet appears once.
[0,0,0] would need three zeros. There are only two.

Constraints:

• 3 to 3,000 numbers.
• Each number is from -100,000 to 100,000.