# Find a triplet that sum to a given value

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. For example, if the given array is {12, 3, 4, 1, 6, 9} and given sum is 24, then there is a triplet (12, 3 and 9) present in array whose sum is 24.

Method 1 (Naive)
A simple method is to generate all possible triplets and compare the sum of every triplet with the given value. The following code implements this simple method using three nested loops.

## C

 `#include ` ` `  `// returns true if there is triplet with sum equal ` `// to 'sum' present in A[]. Also, prints the triplet ` `bool` `find3Numbers(``int` `A[], ``int` `arr_size, ``int` `sum) ` `{ ` `    ``int` `l, r; ` ` `  `    ``// Fix the first element as A[i] ` `    ``for` `(``int` `i = 0; i < arr_size - 2; i++) { ` ` `  `        ``// Fix the second element as A[j] ` `        ``for` `(``int` `j = i + 1; j < arr_size - 1; j++) { ` ` `  `            ``// Now look for the third number ` `            ``for` `(``int` `k = j + 1; k < arr_size; k++) { ` `                ``if` `(A[i] + A[j] + A[k] == sum) { ` `                    ``printf``(``"Triplet is %d, %d, %d"``, ` `                           ``A[i], A[j], A[k]); ` `                    ``return` `true``; ` `                ``} ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``// If we reach here, then no triplet was found ` `    ``return` `false``; ` `} ` ` `  `/* Driver program to test above function */` `int` `main() ` `{ ` `    ``int` `A[] = { 1, 4, 45, 6, 10, 8 }; ` `    ``int` `sum = 22; ` `    ``int` `arr_size = ``sizeof``(A) / ``sizeof``(A); ` `    ``find3Numbers(A, arr_size, sum); ` `    ``return` `0; ` `} `

## Java

 `// Java program to find a triplet ` `class` `FindTriplet { ` ` `  `    ``// returns true if there is triplet with sum equal ` `    ``// to 'sum' present in A[]. Also, prints the triplet ` `    ``boolean` `find3Numbers(``int` `A[], ``int` `arr_size, ``int` `sum) ` `    ``{ ` `        ``int` `l, r; ` ` `  `        ``// Fix the first element as A[i] ` `        ``for` `(``int` `i = ``0``; i < arr_size - ``2``; i++) { ` ` `  `            ``// Fix the second element as A[j] ` `            ``for` `(``int` `j = i + ``1``; j < arr_size - ``1``; j++) { ` ` `  `                ``// Now look for the third number ` `                ``for` `(``int` `k = j + ``1``; k < arr_size; k++) { ` `                    ``if` `(A[i] + A[j] + A[k] == sum) { ` `                        ``System.out.print(``"Triplet is "` `+ A[i] + ``", "` `+ A[j] + ``", "` `+ A[k]); ` `                        ``return` `true``; ` `                    ``} ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``// If we reach here, then no triplet was found ` `        ``return` `false``; ` `    ``} ` ` `  `    ``// Driver program to test above functions ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``FindTriplet triplet = ``new` `FindTriplet(); ` `        ``int` `A[] = { ``1``, ``4``, ``45``, ``6``, ``10``, ``8` `}; ` `        ``int` `sum = ``22``; ` `        ``int` `arr_size = A.length; ` ` `  `        ``triplet.find3Numbers(A, arr_size, sum); ` `    ``} ` `} `

## Python3

 `# Python3 program to find a triplet  ` `# that sum to a given value ` ` `  `# returns true if there is triplet with ` `# sum equal to 'sum' present in A[].  ` `# Also, prints the triplet ` `def` `find3Numbers(A, arr_size, ``sum``): ` ` `  `    ``# Fix the first element as A[i] ` `    ``for` `i ``in` `range``( ``0``, arr_size``-``2``): ` ` `  `        ``# Fix the second element as A[j] ` `        ``for` `j ``in` `range``(i ``+` `1``, arr_size``-``1``):  ` `             `  `            ``# Now look for the third number ` `            ``for` `k ``in` `range``(j ``+` `1``, arr_size): ` `                ``if` `A[i] ``+` `A[j] ``+` `A[k] ``=``=` `sum``: ` `                    ``print``(``"Triplet is"``, A[i], ` `                          ``", "``, A[j], ``", "``, A[k]) ` `                    ``return` `True` `     `  `    ``# If we reach here, then no  ` `    ``# triplet was found ` `    ``return` `False` ` `  `# Driver program to test above function  ` `A ``=` `[``1``, ``4``, ``45``, ``6``, ``10``, ``8``] ` `sum` `=` `22` `arr_size ``=` `len``(A) ` `find3Numbers(A, arr_size, ``sum``) ` ` `  `# This code is contributed by Smitha Dinesh Semwal  `

## C#

 `// C# program to find a triplet ` `// that sum to a given value ` `using` `System; ` ` `  `class` `GFG { ` `    ``// returns true if there is ` `    ``// triplet with sum equal ` `    ``// to 'sum' present in A[]. ` `    ``// Also, prints the triplet ` `    ``static` `bool` `find3Numbers(``int``[] A, ` `                             ``int` `arr_size, ` `                             ``int` `sum) ` `    ``{ ` `        ``// Fix the first ` `        ``// element as A[i] ` `        ``for` `(``int` `i = 0; ` `             ``i < arr_size - 2; i++) { ` ` `  `            ``// Fix the second ` `            ``// element as A[j] ` `            ``for` `(``int` `j = i + 1; ` `                 ``j < arr_size - 1; j++) { ` ` `  `                ``// Now look for ` `                ``// the third number ` `                ``for` `(``int` `k = j + 1; ` `                     ``k < arr_size; k++) { ` `                    ``if` `(A[i] + A[j] + A[k] == sum) { ` `                        ``Console.WriteLine(``"Triplet is "` `+ A[i] + ``", "` `+ A[j] + ``", "` `+ A[k]); ` `                        ``return` `true``; ` `                    ``} ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``// If we reach here, ` `        ``// then no triplet was found ` `        ``return` `false``; ` `    ``} ` ` `  `    ``// Driver Code ` `    ``static` `public` `void` `Main() ` `    ``{ ` `        ``int``[] A = { 1, 4, 45, 6, 10, 8 }; ` `        ``int` `sum = 22; ` `        ``int` `arr_size = A.Length; ` ` `  `        ``find3Numbers(A, arr_size, sum); ` `    ``} ` `} ` ` `  `// This code is contributed by m_kit `

## PHP

 ` `

Output :

```Triplet is 4, 10, 8
```

Time Complexity : O(n^3)

Method 2 (Use Sorting)
Time complexity of the method 1 is O(n^3). The complexity can be reduced to O(n^2) by sorting the array first, and then using method 1 of this post in a loop.
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 using method 1 of this post.

## C++

 `// C++ program to find a triplet ` `#include ` `using` `namespace` `std; ` ` `  `// returns true if there is triplet with sum equal ` `// to 'sum' present in A[]. Also, prints the triplet ` `bool` `find3Numbers(``int` `A[], ``int` `arr_size, ``int` `sum) ` `{ ` `    ``int` `l, r; ` ` `  `    ``/* Sort the elements */` `    ``sort(A, A + arr_size); ` ` `  `    ``/* 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``; ` `} ` ` `  `/* Driver program to test above function */` `int` `main() ` `{ ` `    ``int` `A[] = { 1, 4, 45, 6, 10, 8 }; ` `    ``int` `sum = 22; ` `    ``int` `arr_size = ``sizeof``(A) / ``sizeof``(A); ` ` `  `    ``find3Numbers(A, arr_size, sum); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to find a triplet ` `class` `FindTriplet { ` ` `  `    ``// returns true if there is triplet with sum equal ` `    ``// to 'sum' present in A[]. Also, prints the triplet ` `    ``boolean` `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) { ` `                    ``System.out.print(``"Triplet is "` `+ 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``; ` `    ``} ` ` `  `    ``int` `partition(``int` `A[], ``int` `si, ``int` `ei) ` `    ``{ ` `        ``int` `x = A[ei]; ` `        ``int` `i = (si - ``1``); ` `        ``int` `j; ` ` `  `        ``for` `(j = si; j <= ei - ``1``; j++) { ` `            ``if` `(A[j] <= x) { ` `                ``i++; ` `                ``int` `temp = A[i]; ` `                ``A[i] = A[j]; ` `                ``A[j] = temp; ` `            ``} ` `        ``} ` `        ``int` `temp = A[i + ``1``]; ` `        ``A[i + ``1``] = A[ei]; ` `        ``A[ei] = temp; ` `        ``return` `(i + ``1``); ` `    ``} ` ` `  `    ``/* Implementation of Quick Sort ` `    ``A[] --> Array to be sorted ` `    ``si  --> Starting index ` `    ``ei  --> Ending index ` `     ``*/` `    ``void` `quickSort(``int` `A[], ``int` `si, ``int` `ei) ` `    ``{ ` `        ``int` `pi; ` ` `  `        ``/* Partitioning index */` `        ``if` `(si < ei) { ` `            ``pi = partition(A, si, ei); ` `            ``quickSort(A, si, pi - ``1``); ` `            ``quickSort(A, pi + ``1``, ei); ` `        ``} ` `    ``} ` ` `  `    ``// Driver program to test above functions ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``FindTriplet triplet = ``new` `FindTriplet(); ` `        ``int` `A[] = { ``1``, ``4``, ``45``, ``6``, ``10``, ``8` `}; ` `        ``int` `sum = ``22``; ` `        ``int` `arr_size = A.length; ` ` `  `        ``triplet.find3Numbers(A, arr_size, sum); ` `    ``} ` `} `

## Python3

 `# Python3 program to find a triplet ` ` `  `# returns true if there is triplet ` `# with sum equal to 'sum' present ` `# in A[]. Also, prints the triplet ` `def` `find3Numbers(A, arr_size, ``sum``): ` ` `  `    ``# Sort the elements  ` `    ``A.sort() ` ` `  `    ``# Now fix the first element  ` `    ``# one by one and find the ` `    ``# other two elements  ` `    ``for` `i ``in` `range``(``0``, arr_size``-``2``): ` `     `  ` `  `        ``# To find the other two elements, ` `        ``# start two index variables from ` `        ``# two corners of the array and ` `        ``# move them toward each other ` `         `  `        ``# index of the first element ` `        ``# in the remaining elements ` `        ``l ``=` `i ``+` `1`  `         `  `        ``# index of the last element ` `        ``r ``=` `arr_size``-``1`  `        ``while` `(l < r): ` `         `  `            ``if``( A[i] ``+` `A[l] ``+` `A[r] ``=``=` `sum``): ` `                ``print``(``"Triplet is"``, A[i],  ` `                     ``', '``, A[l], ``', '``, A[r]); ` `                ``return` `True` `             `  `            ``elif` `(A[i] ``+` `A[l] ``+` `A[r] < ``sum``): ` `                ``l ``+``=` `1` `            ``else``: ``# A[i] + A[l] + A[r] > sum ` `                ``r ``-``=` `1` ` `  `    ``# If we reach here, then ` `    ``# no triplet was found ` `    ``return` `False` ` `  `# Driver program to test above function  ` `A ``=` `[``1``, ``4``, ``45``, ``6``, ``10``, ``8``] ` `sum` `=` `22` `arr_size ``=` `len``(A) ` ` `  `find3Numbers(A, arr_size, ``sum``) ` ` `  `# This is contributed by Smitha Dinesh Semwal `

## C#

 `// C# program to find a triplet ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// returns true if there is triplet ` `    ``// with sum equal to 'sum' present ` `    ``// in A[]. Also, prints the triplet ` `    ``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) { ` `                    ``Console.Write(``"Triplet is "` `+ 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``; ` `    ``} ` ` `  `    ``int` `partition(``int``[] A, ``int` `si, ``int` `ei) ` `    ``{ ` `        ``int` `x = A[ei]; ` `        ``int` `i = (si - 1); ` `        ``int` `j; ` ` `  `        ``for` `(j = si; j <= ei - 1; j++) { ` `            ``if` `(A[j] <= x) { ` `                ``i++; ` `                ``int` `temp = A[i]; ` `                ``A[i] = A[j]; ` `                ``A[j] = temp; ` `            ``} ` `        ``} ` `        ``int` `temp1 = A[i + 1]; ` `        ``A[i + 1] = A[ei]; ` `        ``A[ei] = temp1; ` `        ``return` `(i + 1); ` `    ``} ` ` `  `    ``/* Implementation of Quick Sort ` `A[] --> Array to be sorted ` `si --> Starting index ` `ei --> Ending index ` `*/` `    ``void` `quickSort(``int``[] A, ``int` `si, ``int` `ei) ` `    ``{ ` `        ``int` `pi; ` ` `  `        ``/* Partitioning index */` `        ``if` `(si < ei) { ` `            ``pi = partition(A, si, ei); ` `            ``quickSort(A, si, pi - 1); ` `            ``quickSort(A, pi + 1, ei); ` `        ``} ` `    ``} ` ` `  `    ``// Driver Code ` `    ``static` `void` `Main() ` `    ``{ ` `        ``GFG triplet = ``new` `GFG(); ` `        ``int``[] A = ``new` `int``[] { 1, 4, 45, 6, 10, 8 }; ` `        ``int` `sum = 22; ` `        ``int` `arr_size = A.Length; ` ` `  `        ``triplet.find3Numbers(A, arr_size, sum); ` `    ``} ` `} ` ` `  `// This code is contributed by mits `

## PHP

 ` sum ` `                ``\$r``--; ` `        ``} ` `    ``} ` ` `  `    ``// If we reach here, then ` `    ``// no triplet was found ` `    ``return` `false; ` `} ` ` `  `// Driver Code ` `\$A` `= ``array` `(1, 4, 45, 6, 10, 8); ` `\$sum` `= 22; ` `\$arr_size` `= sizeof(``\$A``); ` ` `  `find3Numbers(``\$A``, ``\$arr_size``, ``\$sum``); ` ` `  `// This code is contributed by ajit ` `?> `

Output :

```Triplet is 4, 8, 10
```

Time Complexity : O(n^2)

Method 3 (Hashing Based Solution)

## C++

 `// C++ program to find a triplet using Hashing ` `#include ` `using` `namespace` `std; ` ` `  `// returns true if there is triplet with sum equal ` `// to 'sum' present in A[]. Also, prints the triplet ` `bool` `find3Numbers(``int` `A[], ``int` `arr_size, ``int` `sum) ` `{ ` `    ``// Fix the first element as A[i] ` `    ``for` `(``int` `i = 0; i < arr_size - 2; i++) { ` ` `  `        ``// Find pair in subarray A[i+1..n-1] ` `        ``// with sum equal to sum - A[i] ` `        ``unordered_set<``int``> s; ` `        ``int` `curr_sum = sum - A[i]; ` `        ``for` `(``int` `j = i + 1; j < arr_size; j++) { ` `            ``if` `(s.find(curr_sum - A[j]) != s.end()) { ` `                ``printf``(``"Triplet is %d, %d, %d"``, A[i], ` `                       ``A[j], curr_sum - A[j]); ` `                ``return` `true``; ` `            ``} ` `            ``s.insert(A[j]); ` `        ``} ` `    ``} ` ` `  `    ``// If we reach here, then no triplet was found ` `    ``return` `false``; ` `} ` ` `  `/* Driver program to test above function */` `int` `main() ` `{ ` `    ``int` `A[] = { 1, 4, 45, 6, 10, 8 }; ` `    ``int` `sum = 22; ` `    ``int` `arr_size = ``sizeof``(A) / ``sizeof``(A); ` ` `  `    ``find3Numbers(A, arr_size, sum); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to find a triplet using Hashing ` `import` `java.util.*; ` ` `  `class` `GFG { ` ` `  `    ``// returns true if there is triplet ` `    ``// with sum equal to 'sum' present ` `    ``// in A[]. Also, prints the triplet ` `    ``static` `boolean` `find3Numbers(``int` `A[], ` `                                ``int` `arr_size, ``int` `sum) ` `    ``{ ` `        ``// Fix the first element as A[i] ` `        ``for` `(``int` `i = ``0``; i < arr_size - ``2``; i++) { ` ` `  `            ``// Find pair in subarray A[i+1..n-1] ` `            ``// with sum equal to sum - A[i] ` `            ``HashSet s = ``new` `HashSet(); ` `            ``int` `curr_sum = sum - A[i]; ` `            ``for` `(``int` `j = i + ``1``; j < arr_size; j++) { ` `                ``if` `(s.contains(curr_sum - A[j]) && curr_sum - A[j] != (``int``)s.toArray()[s.size() - ``1``]) { ` `                    ``System.out.printf(``"Triplet is %d, %d, %d"``, A[i], ` `                                      ``A[j], curr_sum - A[j]); ` `                    ``return` `true``; ` `                ``} ` `                ``s.add(A[j]); ` `            ``} ` `        ``} ` ` `  `        ``// If we reach here, then no triplet was found ` `        ``return` `false``; ` `    ``} ` ` `  `    ``/* Driver code */` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `A[] = { ``1``, ``4``, ``45``, ``6``, ``10``, ``8` `}; ` `        ``int` `sum = ``22``; ` `        ``int` `arr_size = A.length; ` ` `  `        ``find3Numbers(A, arr_size, sum); ` `    ``} ` `} ` ` `  `// This code has been contributed by 29AjayKumar `

## Python3

 `# Python3 program to find a triplet using Hashing ` `# returns true if there is triplet with sum equal ` `# to 'sum' present in A[]. Also, prints the triplet ` `def` `find3Numbers(A, arr_size, ``sum``): ` `    ``for` `i ``in` `range``(``0``, arr_size``-``1``): ` `        ``# Find pair in subarray A[i + 1..n-1]  ` `        ``# with sum equal to sum - A[i] ` `        ``s ``=` `set``() ` `        ``curr_sum ``=` `sum` `-` `A[i] ` `        ``for` `j ``in` `range``(i ``+` `1``, arr_size): ` `            ``if` `(curr_sum ``-` `A[j]) ``in` `s: ` `                ``print``(``"Triplet is"``, A[i],  ` `                        ``", "``, A[j], ``", "``, curr_sum``-``A[j]) ` `                ``return` `True` `            ``s.add(A[j]) ` `     `  `    ``return` `False` ` `  `# Driver program to test above function  ` `A ``=` `[``1``, ``4``, ``45``, ``6``, ``10``, ``8``]  ` `sum` `=` `22` `arr_size ``=` `len``(A)  ` `find3Numbers(A, arr_size, ``sum``)  ` ` `  `# This is contributed by Yatin gupta `

## C#

 `// C# program to find a triplet using Hashing ` `using` `System; ` `using` `System.Collections.Generic; ` `public` `class` `GFG { ` ` `  `    ``// returns true if there is triplet ` `    ``// with sum equal to 'sum' present ` `    ``// in A[]. Also, prints the triplet ` `    ``static` `bool` `find3Numbers(``int``[] A, ` `                             ``int` `arr_size, ``int` `sum) ` `    ``{ ` `        ``// Fix the first element as A[i] ` `        ``for` `(``int` `i = 0; i < arr_size - 2; i++) { ` ` `  `            ``// Find pair in subarray A[i+1..n-1] ` `            ``// with sum equal to sum - A[i] ` `            ``HashSet<``int``> s = ``new` `HashSet<``int``>(); ` `            ``int` `curr_sum = sum - A[i]; ` `            ``for` `(``int` `j = i + 1; j < arr_size; j++) { ` `                ``if` `(s.Contains(curr_sum - A[j])) { ` `                    ``Console.Write(``"Triplet is {0}, {1}, {2}"``, A[i], ` `                                  ``A[j], curr_sum - A[j]); ` `                    ``return` `true``; ` `                ``} ` `                ``s.Add(A[j]); ` `            ``} ` `        ``} ` ` `  `        ``// If we reach here, then no triplet was found ` `        ``return` `false``; ` `    ``} ` ` `  `    ``/* Driver code */` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int``[] A = { 1, 4, 45, 6, 10, 8 }; ` `        ``int` `sum = 22; ` `        ``int` `arr_size = A.Length; ` ` `  `        ``find3Numbers(A, arr_size, sum); ` `    ``} ` `} ` ` `  `/* This code contributed by PrinciRaj1992 */`

Output :

```Triplet is 4, 8, 10
```

How to print all triplets with given sum?
Please refer Find all triplets with zero sum

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

code

load comments