3Sum: Triplets Summing to Zero

Problem Given an integer array, find all unique triplets [a, b, c] drawn from three distinct indices such that a + b + c = 0.

Input / Output

• Input: an integer array nums.
• Output: a list of every unique triplet summing to zero, in any order; the same value multiset must never appear twice.

Constraints

• 3 <= n <= 3000; values may repeat and may be negative.
• The triplet must use three distinct indices, though equal values at different indices are perfectly legal.
• Duplicate triplets must be suppressed — this, not the search itself, is the real difficulty of the problem.

Example

• [-1,0,1,2,-1,-4] -> [[-1,-1,2],[-1,0,1]]. The triplet [-1,-1,2] legitimately uses both -1s, while the second -1 must not regenerate [-1,0,1] a second time.
• [0,0,0,0] -> [[0,0,0]] — one triplet, not four.
• [1,2,3] -> [].