Given an integer array arr of size n , are there elements x, y, z in arr such that x + y + z = 0 ? Find all unique triplets in the array which gives the sum equal to zero.

Problem Note

• The solution set must not contain duplicate triplets.
• Triplet must be in ascending order. (i.e. x ≤ y ≤ z)

Example 1

Input: arr[]= [0, -1, 2, -3, 1]
Output: [[-3, 1, 2],[-1, 0, 1]]
Explanation: In the above example, the sum of the triplet [2, -3, 1] and [0, -1, 1] is equal to 0(2 + (-3) + 1 = 0 and 0 + (-1) + 1 = 0). But they are not in ascending order, so the output in ascending order is [-3, 1, 2] and [-1, 0, 1].

Example 2

Input: arr[] = [1, -2, 1, 0, 5]
Output: [[-2, 1, 1]]
Explanation: In the above example, the sum of the triplet [1, -2, 1] is equal to 0(1 + (-2) + 1 = 0). But it is not in ascending order, so the output in ascending order is [-2, 1, 1].