Three Sum Problem

Given an array of integers and a target integer \(T\), determine if there exist three distinct numbers in the array whose sum equals \(T\). If such a triplet exists, output YES; otherwise, output NO.

The efficient solution typically involves first sorting the array and then using the two-pointer technique. The expected time complexity is \(O(n^2)\), where \(n\) is the number of elements in the array.

inputFormat

The first line contains an integer \(n\) representing the number of elements in the array.

The second line contains \(n\) space-separated integers, which are the elements of the array.

The third line contains a single integer \(T\), the target sum.

outputFormat

Output a single line containing YES if there exists a triplet in the array that sums to \(T\); otherwise, output NO.

5
1 2 3 4 5
9

YES