Three Numbers That Sum to Zero

Write three_sum_zero(nums) that finds every triplet of numbers, taken from three different positions in nums, whose sum is exactly 0. Return them as a list of lists. Write each triplet in ascending order, sort the list of triplets in ascending order too, and list each combination of values only once, even when it can be built from different positions.

Examples

three_sum_zero([-2, 0, 1, 1, 2, -1])   # returns [[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
three_sum_zero([0, 0, 0, 0])           # returns [[0, 0, 0]]
three_sum_zero([1, 2, -4])             # returns []

In the first example, [-1, 0, 1] can be made with either of the two 1s, but it is listed once. [-2, 1, 1] uses both 1s, which is allowed because they sit at different positions.

Constraints

• 0 <= len(nums) <= 3,000
• -10^5 <= nums[i] <= 10^5

Note

3,000 numbers have about 4.5 billion triplets, far too many to try one by one. Aim for a number of steps that grows like the square of the length.