606. Every Distinct Triple That Adds to Zero
Given n integers, find every set of three values that adds to zero. Two triples are the SAME
when they use the same three values, however they were arranged or wherever they came from.
Print how many distinct triples there are, then the triples themselves, each with its values in non-decreasing order, one per line, in increasing lexicographic order.
-1 0 1 2 -1 -4 -> 2
-1 -1 2
-1 0 1
1 2 3 -> 0
## Not the same question as problem 120
Problem 120 counts triples of POSITIONS, so repeated values give separate triples and the
answer there is a number. This asks for distinct VALUE triples and prints them, so duplicates
must be collapsed. On 0 0 0 0 problem 120 counts 4 and this answers 1.
Being clear which of the two is wanted is most of the work, and it is the first thing to settle before writing any loop.
## Sort, fix one, sweep the rest
sort the array
for i from 0 to n-3:
lo = i+1, hi = n-1
while lo < hi:
s = a[i] + a[lo] + a[hi]
s < 0 -> lo += 1
s > 0 -> hi -= 1
s == 0 -> record, then move BOTH inward
With a[i] fixed, the inner loop is exactly problem 605 looking for -a[i], and its
correctness argument carries over unchanged.
Sorting costs O(n log n) and the sweeps cost O(n^2), so the whole thing is O(n^2), down
from the O(n^3) of three nested loops.
## Skipping duplicates, in three places
This is where the problem is won or lost, and each skip has its own reason:
· for the OUTER index: if a[i] == a[i-1], skip. Every triple starting with this value was
already produced when the earlier copy was the outer element.
· after recording, advance lo past equal values, and pull hi back past equal values.
Otherwise the very next step records the same triple again.
Sorting is what makes all three possible: equal values are adjacent, so "already seen" is a comparison with the neighbour rather than a set lookup.
## Why the output order comes free
The outer loop runs over increasing a[i], and for a fixed a[i] the recorded a[lo]
increases as lo advances. So triples are produced in lexicographic order already and no
final sort is needed.
## Boundaries
Fewer than three values gives 0 triples and prints only the count.
0 0 0 gives exactly one triple. So does 0 0 0 0, which is the duplicate test.
## Cost
Time O(n^2). Space O(1) beyond the input and the output.
Constraints - `0 ≤ n ≤ 3000` - `-10^9 ≤ each value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n integers. It is absent when n is 0.
Output
Print the number of distinct triples on the first line. Then print each triple on its own line, values in non-decreasing order separated by single spaces, the lines in increasing lexicographic order.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.