A lab has n weights, each with a signed calibration error. Find every distinct set of three weights (by value) whose errors add up to exactly 0.
Print how many such trios there are, then each trio on its own line in ascending order inside the trio, with trios sorted in ascending order.
Constraints
- 0 ≤ n ≤ 2000
- −100000 ≤ value ≤ 100000
Input and output
- Input
- Line 1: n. Line 2: n integers.
- Output
- Line 1: the number of trios k. Then k lines, each with three integers in ascending order. Trios sorted lexicographically.
Examples
Input 1
6
-2 0 1 1 2 -1Output
3
-2 0 2
-2 1 1
-1 0 1Three distinct trios: −2 0 2, −2 1 1 and −1 0 1.
Input 2
3
1 2 3Output
0No three values add to zero.
Show hints
- Sort first.
- Fix the smallest value, then look for the other two with two pointers moving inwards.
- Skip repeated values so each trio is reported once.
Show the explanation
After sorting, fix index i as the smallest member and search the rest with two pointers l and r. If the sum is too small, move l right; too large, move r left; zero, record it and move both past any duplicates. Skipping a value of i equal to the previous one prevents repeats. Sorting costs O(n log n) and the scan O(n²) overall, compared with O(n³) for trying every triple.
Original UniCircle question. Last reviewed 22 Oct 2026.