9. 3Sum

Medium · Array

Given an array of integers, find all unique triplets (three numbers) that sum to zero. Return each triplet as a sorted array, and sort the list of triplets in ascending order. For example, in [-1,0,1,2,-1,-4], the triplets [-1,-1,2] and [-1,0,1] both sum to 0. Avoid duplicates in your result: even though -1 appears twice in the input, each triplet should appear only once in the output.

Examples

Example 1
Input: [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation: two unique triplets sum to 0
Example 2
Input: [0, 0, 0]
Output: [[0, 0, 0]]
Explanation: one triplet of zeros

Constraints