Solution: Triplet Sum to Zero

## Problem Statement

Given an array of unsorted numbers, find all unique triplets in it that add up to zero.

Example 1:

``````Input: [-3, 0, 1, 2, -1, 1, -2]
Output: [[-3, 1, 2], [-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
Explanation: There are four unique triplets whose sum is equal to zero. smallest sum.'
``````

Example 2:

``````Input: [-5, 2, -1, -2, 3]
Output: [[-5, 2, 3], [-2, -1, 3]]
Explanation: There are two unique triplets whose sum is equal to zero.
``````

## Solution

This problem follows the Two Pointers pattern and shares similarities with Pair with Target Sum. A couple of differences are that the input array is not sorted and instead of a pair we need to find triplets with a target sum of zero.

To follow a similar approach, first, we will sort the array and then iterate through it taking one number at a time. Let’s say during our iteration we are at number ‘X’, so we need to find ‘Y’ and ‘Z’ such that X + Y + Z == 0. At this stage, our problem translates into finding a pair whose sum is equal to “-X” (as from the above equation Y + Z==−X).

Another difference from `Pair with Target Sum` is that we need to find all the unique triplets. To handle this, we have to skip any duplicate number. Since we will be sorting the array, so all the duplicate numbers will be next to each other and are easier to skip.

Here is the detailed walk through of the algorithm:

1. The method `searchTriplets` is the main method that orchestrates the process. The algorithm starts by sorting the input array.

2. It then starts iterating over the array. For each element, it calls the method `searchPair` to find pairs in the rest of the array that add up to the negative value of the current element. The purpose of this is to find three numbers that add up to zero (i.e., the current number and two other numbers that add up to the negative of the current number).

3. The `searchPair` method uses the two-pointer technique to find pairs that add up to a given target. It starts with one pointer at the beginning of the array (or the index after the current number) and another pointer at the end of the array. It calculates the sum of the numbers at the pointers, and if the sum is equal to the target, it adds a triplet consisting of the negative target (which is the number we're currently processing in the `searchTriplets` method) and the two numbers that make up the sum to the result list.

4. If the sum is less than the target, it means we need to increase the sum, so we move the left pointer one step to the right. If the sum is greater than the target, it means we need to decrease the sum, so we move the right pointer one step to the left.

5. To avoid adding duplicate triplets to the list, the algorithm skips elements that are the same as the previous element both in the `searchTriplets` method and in the `searchPair` method.

In the end, the `searchTriplets` method returns a list of all unique triplets in the array that add up to zero.

## Code

Here is what our algorithm will look like:

NaN
NaN