CareerCup

This problem is called 3-SUM and there is no currently known way to solve it faster than O(n^2). This is actually an important problem because a number of problems that are not known to admit sub-quadratic time solutions can be reduced to this one in sub-quadratic time, which means we'd have asymptotically faster algorithms for all of them if we could solve this one in less than O(n^2). You would likely win some kind of prize if you managed to give such a solution.

FFT can solve the problem in O(N + R log R) where R is the range of the numbers and N is the number of elements, but since R can be very large in comparison to N, this solution is not general.

int a[] = {3, 1, 4, 2, 9, 10, 33, 42, 2, 0, 6};
    int N = sizeof(a) / sizeof(*a);

    sort(a, a + N);
    int K = 12;

    for (int i = 0; i < N - 3; i++) {
        for (int j = i + 1; j < N - 2; j++) {
            int diff = K - a[i] - a[j];
            int *t = lower_bound(a + j, a + N, diff);

            if (t != a + N && *t == diff) {
                cout << "(" << a[i] << ", " << a[j] << ", " << *t << ")" << endl;
            }
        }

I am avoiding additional comparisons while comparing partialSum with K:

public static void printTripletSumUpToK(int[] nums, int k) {

    // basic validation
    if (nums == null || nums.length < 3) {
        System.out.println("Invalid inputs");
    }
    
    List<String> triplets = new ArrayList<String>();
    int len = nums.length;
    int partialSum = 0;
    
    for (int i = 0; i < len - 2; i++) {
        partialSum = nums[i];
        if (partialSum < k) {
            for (int j = i + 1; j < len - 1; j++) {
            	partialSum = nums[i] + nums[j];
                 if (partialSum < k) {
                	 
                	 for (int z = j + 1; z < len; z++) {
                		 partialSum = nums[i] + nums[j] + nums[z];
                         if (partialSum == k) {
                        	 
                        	 String tripletSum = nums[i]+"+"+nums[j]+"+"+nums[z]+"="+k;
                        	 
                        	 if (!triplets.contains(tripletSum)) {
                        		 triplets.add(tripletSum);
                        	 }
                        	                                 
                         } 
                	 }                	 
                                                       
                 }
            }
        }
    }
    
    System.out.println(triplets);
}