Find a triplet that sum to a given value | GeeksforGeeks

Find a triplet that sum to a given value | GeeksforGeeks
Given an array and a value, find if there is a triplet in array whose sum is equal to the given value. If there is such a triplet present in array, then print the triplet and return true. Else return false
1) Sort the input array.
2) Fix the first element as A[i] where i is from 0 to array size – 2. After fixing the first element of triplet, find the other two elements

bool find3Numbers(int A[], int arr_size, int sum)

{

    int l, r;

    /* Sort the elements */

    quickSort(A, 0, arr_size-1);

    /* Now fix the first element one by one and find the

       other two elements */

    for (int i = 0; i < arr_size - 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 = arr_size-1; // index of the last element

        while (l < r)

        {

            if( A[i] + A[l] + A[r] == sum)

            {

                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;

}

Given an array of distinct numbers, how do we count the number of triplets with given sum?

http://comproguide.blogspot.com/2014/12/counting-triplets-with-given-sum.html

public static int getTripletWithSum(int[] array, int sum)


{


Arrays.sort(array);


int tripletCount = 0;


for(int i = 0; i < array.length-2; i++ )


{


for(int j = i+1, k = array.length-1; j < k; )


{


int curSum = array[i] + array[j] + array[k];


if( curSum == sum )


{


System.out.println(array[i] + " " + array[j] + " " + array[k]);


j++;


k--;


tripletCount++;


}


else if( curSum < sum )


{


j++;


}


else


{


k--;


}


}


}


return tripletCount;


}


 


public static int getTripletWithSumOrLess(int[] array, int sum)


{


Arrays.sort(array);


int tripletCount = 0;


for(int i = 0; i < array.length-2; i++ )


{


for(int j = i+1, k = array.length-1; j < k; )


{


int curSum = array[i] + array[j] + array[k];


if( curSum <= sum )


{


tripletCount += k-j;


j++;


k--;


}


else


{


k--;


}


}


}


return tripletCount;


}

Read full article from Find a triplet that sum to a given value | GeeksforGeeks