#168MediumTwo Pointers· Sort and Squeeze

Zero-Sum Ledger Triples

An auditor receives a ledger of signed adjustments: positive numbers are credits and negative numbers are debits. She is looking for groups of **three different entries** whose amounts cancel out exactly, summing to zero. Return every distinct triple of values `[a, b, c]` that can be chosen from three different positions of `ledger` with `a + b + c = 0`. Two triples are the same if they contain the same values, regardless of which positions they came from. Report each triple in non-decreasing order (`a <= b <= c`), and list the triples in ascending lexicographic order, so the result is unique. If no triple exists, return an empty list.

Input format

`ledger`: an array of integers.

Output format

An array of triples `[a, b, c]`, each sorted ascending, with the list sorted lexicographically and no repeated triple.

Examples

Input: ledger = [-1, 0, 1, 2, -1, -4]

Output: [[-1, -1, 2], [-1, 0, 1]]

The values -1, -1, 2 and -1, 0, 1 both cancel out. The two -1 entries are separate positions, so [-1, -1, 2] is allowed.

Input: ledger = [0, 1, 1]

Output: []

No three entries sum to zero.

Input: ledger = [0, 0, 0, 0]

Output: [[0, 0, 0]]

Any three zeros work, but all such choices are the same triple of values, so it is reported once.

Constraints

3 <= ledger.length <= 3000
-10^5 <= ledger[i] <= 10^5

#two-pointers
#sorting
#arrays
#deduplication