ThreeSum.java

class Solution{
	boolean threeSumBruteForce(int arr[], int sum)
	{	 
		int n = arr.length;
	    // Fix the first element as A[i]
	    for (int i = 0; i < n-2; i++)
	    {
	       // Fix the second element as A[j]
	       for (int j = i+1; j < n-1; j++)
	       {
	           // Now look for the third number
	           for (int k = j+1; k < n; k++)
	           {
	               if (arr[i] + arr[j] + arr[k] == sum)
	               {
	                 System.out.printf("Triplet is %d, %d, %d", arr[i], arr[j], arr[k]);
	                 return true;
	               }
	           }
	       }
	    }
	 
	    // If we reach here, then no triplet was found
	    return false;
	}
	
		boolean threeSumSorting(int A[], int sum)
	{
	    int l, r;
	    int n = A.length;
	    Arrays.sort(A);
	 
	    // Now fix the first element one by one and find the
	    //   other two elements 
	    for (int i = 0; i < n - 2; i++)
	    {
	 
	        // To find the other two elements, start two index variables
	        // from two corners of the array and move them toward each
	        // other
	        l = i + 1; // index of the first element in the remaining elements
	        r = n-1; // index of the last element
	        while (l < r)
	        {
	            if( A[i] + A[l] + A[r] == sum)
	            {
	                System.out.printf("Triplet is %d, %d, %d", A[i], A[l], A[r]);
	                return true;
	            }
	            else if (A[i] + A[l] + A[r] < sum)
	                l++;
	            else // A[i] + A[l] + A[r] > sum
	                r--;
	        }
	    }
	 
	    // If we reach here, then no triplet was found
	    return false;
	}
}