Find Unique Triplets Summing to Target

Given an array of integers, your task is to find all unique triplets in the array that sum to a specified target value. Each triplet must be displayed in non-decreasing order (i.e. sorted in ascending order) and the overall list of triplets should be in lexicographical order.

If no valid triplet exists, output [].

For example, consider the array [1, 0, -1, 2, -1, -4] and target value 0. After sorting, the array becomes [-4, -1, -1, 0, 1, 2]. The valid unique triplets are:

• [-1, -1, 2]
• [-1, 0, 1]

inputFormat

The input is read from stdin and has the following format:

n
num1 num2 ... numn
target

where:

• n is the number of integers in the array.
• The second line contains n space-separated integers.
• The third line is a single integer representing the target sum.

outputFormat

The output should be printed to stdout.

If there exists at least one triplet, print each triplet in a separate line with the three numbers separated by a single space. If no valid triplet exists, print [] (without quotes).

## sample

6
1 0 -1 2 -1 -4
0

-1 -1 2
-1 0 1

</p>