Given an array A[ ] of n integers, are there elements x, y, z in A such that x + y + z = 0? Find all unique triplets in the array which gives the sum of zero.

Problem Note

  • The solution set must not contain duplicate triplets.
  • Triplet must be in non-descending order. (i.e. a ≤ b ≤ c)

Example 1

Input: A[]= [-1, 0, 1, 2, -1, -4]
Output: [[-1, 0, 1],[-1, -1, 2]]

Example 2

Input: A[] = [1, -2, 1, 0, 5]
Output: [[1, 1, -2]]