Triplets Summing to Zero

You are given an array of n integers. Find all unique triplets of positions whose values sum to zero. A triplet is unique by its multiset of values: the same combination of three numbers must not be reported more than once even if it can be formed from different positions in the array.

Input: The first line contains the integer n. The second line contains n space-separated integers. Output: Print each unique triplet on its own line as three space-separated integers in non-decreasing order (a <= b <= c). Triplets must be printed in non-decreasing order of their first element, then second, then third. If no such triplet exists, print nothing.

3 <= n <= 3000 -10^5 <= arr[i] <= 10^5

This is the foundational 'fix one, two-pointer the rest' pattern that extends directly to 'Quadruplets Summing to Target' (fix two, two-pointer the rest) - recognizing this extensible pattern makes the harder k-sum variants feel like natural extensions rather than new problems.

Find every unique triplet of values in an array that sums to zero, using sorting plus two pointers. Brute force: Check every possible triplet of positions directly with three nested loops - this costs O(n³), too slow for larger arrays, and also needs extra work to detect and skip duplicate triplets. Optimised: Sorting FIRST enables both the two-pointer technique (fixing one element, then scanning the rest with two pointers for a target sum) AND easy duplicate detection (identical values become ADJACENT after sorting, so skipping them is a simple adjacent-check) - reducing the search from O(n³) to O(n²).

1. Sort the array first - this both enables the two-pointer scan and makes duplicate triplets easy to skip. 2. Fix ONE element at a time (the smallest of the triplet), then use TWO POINTERS on the remaining sorted sub-array to find pairs summing to its NEGATION. 3. After finding a valid triplet, skip over any following DUPLICATE values at each of the three positions to avoid reporting the same triplet twice.

Time: O(n²) - sorting costs O(n log n), and for each of the n fixed elements, a two-pointer scan costs O(n). Space: O(1) extra space beyond the sort itself (or O(n) if the sort isn't in-place).

Handle an array with no zero-summing triplet at all (no output) and arrays with many repeated values where duplicate triplets must be suppressed; sort first, then use two pointers per fixed first element to stay within O(n^2) at n = 3000.

Be ready to explain the duplicate-skipping logic precisely - skipping duplicate values at ALL THREE positions (the fixed element, and both pointers) is necessary to avoid reporting the same VALUE-triplet more than once, even though it could technically be formed from different index combinations.