Three Sum Problem

Given an array of integers, find all unique triplets in the array such that the sum of the three numbers is zero. Each triplet must be output in non-decreasing order and no duplicate triplets are allowed. An efficient solution with expected O(n²) time complexity is required.

In other words, let the array be \( arr \) of length \( n \). You need to find all distinct triples \( (a, b, c) \) such that:

[ a + b + c = 0 ]

and \( a \le b \le c \). If there are no triplets that satisfy the condition, output nothing.

inputFormat

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

outputFormat

For each found triplet, output a line with three space-separated integers in non-decreasing order. The order of the lines does not matter. If no triplet exists, output nothing.## sample

6
-1 0 1 2 -1 -4

-1 -1 2
-1 0 1