Triplet Sum

Languages

Given an integer array numbers, return all triplets [numbers[i], numbers[j], numbers[k]] such that i, j, and k are distinct indices and their values sum to 0. Ensure that the solution set contains no duplicate triplets.

Input

  • numbers: number[]: An array of integers

Notes

  • Output should be in sorted order

Examples

Input: numbers = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: numbers[0] + numbers[1] + numbers[2] = (-1) + 0 + 1 = 0. numbers[1] + numbers[2] + numbers[4] = 0 + 1 + (-1) = 0. numbers[0] + numbers[3] + numbers[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]
Input: numbers = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet adds up to 0
Input: numbers = [1,0,0]
Output: []
Explanation: The only possible triplet does not add up to 0

Constraints

  • 3 <= numbers.length <= 1000
  • -10,000 <= numbers[i] <= 10,000