Three Sum Problem

You are given an array of integers (which may contain duplicates) and your task is to find all unique triplets \( (a, b, c) \) in the array such that the sum \( a+b+c=0 \). Each triplet must have its elements in non-descending order. The final list of triplets should be sorted in lexicographical order; that is, sorted by the first element, then the second, and so on.

Constraints:

• \( 3 \leq n \leq 3000 \), where \( n \) is the number of elements in the array.
• Each integer \( x \) in the array satisfies \( -10^5 \leq x \leq 10^5 \).

If there is no such triplet, output an empty list: [].

Example 1:
Input: 6 followed by -1 0 1 2 -1 -4
Output: [[-1, -1, 2], [-1, 0, 1]]

Example 2:
Input: 4 followed by 0 0 0 0
Output: [[0, 0, 0]]

inputFormat

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

outputFormat

Output a single line representing the list of unique triplets. Each triplet should be displayed as a list in the format [a, b, c]. The entire output should be a list of these triplets. If no triplet exists, output [].

6
-1 0 1 2 -1 -4

[[-1, -1, 2], [-1, 0, 1]]