3Sum: Find All Unique Triplets

Given an array of integers, find all unique triplets such that the sum of the three numbers is zero.

The answer must not include duplicate triplets. Each triplet should be printed in non-decreasing order, and the overall list of triplets must be sorted in lexicographical order.

For example, given the input array [-1, 0, 1, 2, -1, -4], the expected output is:
-1 -1 2
-1 0 1

The problem can be expressed in mathematical terms as finding all unique triplets ( (a, b, c) ) from the array such that ( a + b + c = 0 ).

inputFormat

The first line of input contains an integer ( n ) representing the number of elements in the array. The second line contains ( n ) space-separated integers.

outputFormat

Output each unique triplet on a new line, with the three integers separated by a single space. The triplets must be in non-decreasing order and the overall set must be sorted lexicographically. If no triplet exists, output nothing.## sample

6
-1 0 1 2 -1 -4

-1 -1 2
-1 0 1