Find Triplet Sum to Zero

Given an array of integers, the goal is to find all unique triplets (sets of three numbers) within the array that sum up to exactly zero. This is a fundamental problem in computational geometry and algorithm design, often encountered in data analysis and searching for patterns in datasets.

Problem Description

You are tasked with implementing a function that takes an array of integers as input and returns a list of all unique triplets, where each triplet consists of three distinct numbers from the input array that sum to zero.

Key Requirements:

Find Triplet Sum: Identify sets of three numbers (a, b, c) from the input array such that a + b + c = 0.
Uniqueness: The solution set must not contain duplicate triplets. For example, if the input array contains multiple instances of the same number, you should only return a triplet once, even if it can be formed in different ways using those duplicate numbers. The order of numbers within a triplet does not matter for uniqueness (e.g., [-1, 0, 1] is the same triplet as [0, -1, 1]).
Distinct Elements: Each triplet must consist of three distinct elements from the input array. This means you cannot use the same element at the same index multiple times within a single triplet.
Return Format: The output should be a list of lists, where each inner list represents a unique triplet.

Edge Cases to Consider:

Arrays with fewer than three elements.
Arrays containing only positive numbers.
Arrays containing only negative numbers.
Arrays containing zeros.
Arrays with duplicate numbers.

Examples

Example 1:

Input: [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation:
The triplets that sum to zero are:
(-1) + 0 + 1 = 0
(-1) + (-1) + 2 = 0
The triplet [-1, 0, 1] can be formed using the first -1, 0, and 1.
The triplet [-1, -1, 2] can be formed using the two -1s and 2.
Note that [0, 1, -1] is considered the same triplet as [-1, 0, 1].

Example 2:

Input: [0, 1, 1]
Output: []
Explanation: No triplets sum to zero.

Example 3:

Input: [0, 0, 0]
Output: [[0, 0, 0]]
Explanation: The only triplet that sums to zero is [0, 0, 0].

Example 4:

Input: [-2, 0, 0, 2, 2]
Output: [[-2, 0, 2]]
Explanation:
The triplet [-2, 0, 2] sums to zero. Even though there are multiple 0s and 2s, we only include this triplet once.

Constraints

The input array will contain between 0 and 3000 elements, inclusive.
Each element in the input array will be an integer between -10^5 and 10^5, inclusive.
The algorithm should aim for a time complexity better than O(n^3).

Notes

Consider how sorting the input array might simplify the process of finding triplets and handling duplicates.
Think about strategies to efficiently check for the third number needed to form a sum of zero, once two numbers have been selected.
The requirement for unique triplets means you'll need a way to avoid adding the same combination of numbers multiple times, even if they appear in different orders or are formed using different indices of duplicate values.

Problem Description

Key Requirements:

Find Triplet Sum: Identify sets of three numbers (a, b, c) from the input array such that a + b + c = 0.

Uniqueness: The solution set must not contain duplicate triplets. For example, if the input array contains multiple instances of the same number, you should only return a triplet once, even if it can be formed in different ways using those duplicate numbers. The order of numbers within a triplet does not matter for uniqueness (e.g., [-1, 0, 1] is the same triplet as [0, -1, 1]).

Distinct Elements: Each triplet must consist of three distinct elements from the input array. This means you cannot use the same element at the same index multiple times within a single triplet.

Return Format: The output should be a list of lists, where each inner list represents a unique triplet.

Edge Cases to Consider:

Arrays with fewer than three elements.

Arrays containing only positive numbers.

Arrays containing only negative numbers.

Arrays containing zeros.

Arrays with duplicate numbers.

Examples

Example 1:

Input: [-1, 0, 1, 2, -1, -4] Output: [[-1, -1, 2], [-1, 0, 1]] Explanation: The triplets that sum to zero are: (-1) + 0 + 1 = 0 (-1) + (-1) + 2 = 0 The triplet [-1, 0, 1] can be formed using the first -1, 0, and 1. The triplet [-1, -1, 2] can be formed using the two -1s and 2. Note that [0, 1, -1] is considered the same triplet as [-1, 0, 1].

Example 2:

Input: [0, 1, 1] Output: [] Explanation: No triplets sum to zero.

Example 3:

Input: [0, 0, 0] Output: [[0, 0, 0]] Explanation: The only triplet that sums to zero is [0, 0, 0].

Example 4:

Input: [-2, 0, 0, 2, 2] Output: [[-2, 0, 2]] Explanation: The triplet [-2, 0, 2] sums to zero. Even though there are multiple 0s and 2s, we only include this triplet once.

Notes

Consider how sorting the input array might simplify the process of finding triplets and handling duplicates.

Think about strategies to efficiently check for the third number needed to form a sum of zero, once two numbers have been selected.

The requirement for unique triplets means you'll need a way to avoid adding the same combination of numbers multiple times, even if they appear in different orders or are formed using different indices of duplicate values.