The 3SUM problem asks if a given set of numbers contains three elements that sum to zero.
void ThreeSum(int S [], int n)
{
// Assumes S is sorted in increasing order
int a, b, c, start, end;
for (int i = 0; i <= n - 3; i++)
{
a = S[i];
start = i + 1;
end = n - 1;
while (start < end)
{
b = S[start];
c = S[end];
if (a + b + c == 0)
{
std::cout << "3SUM: " << a << ", " << b << ", " << c << "\n";
start = start + 1;
end = end - 1;
}
else if (a + b + c > 0)
{
end = end - 1;
}
else
{
start = start + 1;
}
}
}
}