# Find all triplets with zero sum

Given an array of distinct elements. The task is to find triplets in array whose sum is zero.

Examples :

```Input : arr[] = {0, -1, 2, -3, 1}
Output : 0 -1 1
2 -3 1

Input : arr[] = {1, -2, 1, 0, 5}
Output : 1 -2  1
```

Method 1 (Simple : O(n3))
The naive approach is that run three loops and check one by one that sum of three elements is zero or not if sum of three elements is zero then print elements other wise print not found.

## C++

 `// A simple C++ program to find three elements ` `// whose sum is equal to zero ` `#include ` `using` `namespace` `std; ` ` `  `// Prints all triplets in arr[] with 0 sum ` `void` `findTriplets(``int` `arr[], ``int` `n) ` `{ ` `    ``bool` `found = ``true``; ` `    ``for` `(``int` `i=0; i

## Java

 `// A simple Java program to find three elements ` `// whose sum is equal to zero ` `class` `num{ ` `// Prints all triplets in arr[] with 0 sum ` `static` `void` `findTriplets(``int``[] arr, ``int` `n) ` `{ ` `    ``boolean` `found = ``true``; ` `    ``for` `(``int` `i=``0``; i

## Python3

 `# A simple Python 3 program  ` `# to find three elements whose  ` `# sum is equal to zero ` ` `  `# Prints all triplets in  ` `# arr[] with 0 sum ` `def` `findTriplets(arr, n): ` ` `  `    ``found ``=` `True` `    ``for` `i ``in` `range``(``0``, n``-``2``): ` `     `  `        ``for` `j ``in` `range``(i``+``1``, n``-``1``): ` `         `  `            ``for` `k ``in` `range``(j``+``1``, n): ` `             `  `                ``if` `(arr[i] ``+` `arr[j] ``+` `arr[k] ``=``=` `0``): ` `                    ``print``(arr[i], arr[j], arr[k]) ` `                    ``found ``=` `True` `     `  `             `  `    ``# If no triplet with 0 sum  ` `    ``# found in array ` `    ``if` `(found ``=``=` `False``): ` `        ``print``(``" not exist "``) ` ` `  `# Driver code ` `arr ``=` `[``0``, ``-``1``, ``2``, ``-``3``, ``1``] ` `n ``=` `len``(arr) ` `findTriplets(arr, n) ` ` `  `# This code is contributed by Smitha Dinesh Semwal     `

/div>

## C#

 `// A simple C# program to find three elements  ` `// whose sum is equal to zero ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// Prints all triplets in arr[] with 0 sum ` `    ``static` `void` `findTriplets(``int` `[]arr, ``int` `n) ` `    ``{ ` `        ``bool` `found = ``true``; ` `        ``for` `(``int` `i = 0; i < n-2; i++) ` `        ``{ ` `            ``for` `(``int` `j = i+1; j < n-1; j++) ` `            ``{ ` `                ``for` `(``int` `k = j+1; k < n; k++) ` `                ``{ ` `                    ``if` `(arr[i] + arr[j] + arr[k] ` `                                           ``== 0) ` `                    ``{ ` `                        ``Console.Write(arr[i]); ` `                        ``Console.Write(``" "``); ` `                        ``Console.Write(arr[j]); ` `                        ``Console.Write(``" "``); ` `                        ``Console.Write(arr[k]); ` `                        ``Console.Write(````" "````); ` `                        ``found = ``true``; ` `                    ``} ` `                ``} ` `            ``} ` `        ``} ` `     `  `        ``// If no triplet with 0 sum found in  ` `        ``// array ` `        ``if` `(found == ``false``) ` `            ``Console.Write(``" not exist "``); ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `[]arr = {0, -1, 2, -3, 1}; ` `        ``int` `n = arr.Length; ` `        ``findTriplets(arr, n); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal. `

## PHP

 ` `

Output:

```0 -1 1
2 -3 1```

Time Complexity : O(n3)
Auxiliary Space : O(1)

Method 2 (Hashing : O(n2))
We iterate through every element. For every element arr[i], we find a pair with sum “-arr[i]”. This problem reduces to pairs sum and can be solved in O(n) time using hashing.

```Run a loop from i=0 to n-2
Create an empty hash table
Run inner loop from j=i+1 to n-1
If -(arr[i] + arr[j]) is present in hash table
print arr[i], arr[j] and -(arr[i]+arr[j])
Else
Insert arr[j] in hash table.
```

## C++

 `// C++ program to find triplets in a given ` `// array whose sum is zero ` `#include ` `using` `namespace` `std; ` ` `  `// function to print triplets with 0 sum ` `void` `findTriplets(``int` `arr[], ``int` `n) ` `{ ` `    ``bool` `found = ``false``; ` ` `  `    ``for` `(``int` `i=0; i s; ` `        ``for` `(``int` `j=i+1; j

## Java

 `// Java program to find triplets in a given ` `// array whose sum is zero ` `import` `java.util.*; ` ` `  `class` `GFG  ` `{ ` ` `  `    ``// function to print triplets with 0 sum ` `    ``static` `void` `findTriplets(``int` `arr[], ``int` `n)  ` `    ``{ ` `        ``boolean` `found = ``false``; ` ` `  `        ``for` `(``int` `i = ``0``; i < n - ``1``; i++)  ` `        ``{ ` `            ``// Find all pairs with sum equals to ` `            ``// "-arr[i]" ` `            ``HashSet s = ``new` `HashSet(); ` `            ``for` `(``int` `j = i + ``1``; j < n; j++)  ` `            ``{ ` `                ``int` `x = -(arr[i] + arr[j]); ` `                ``if` `(s.contains(x))  ` `                ``{ ` `                    ``System.out.printf(````"%d %d %d "````, x, arr[i], arr[j]); ` `                    ``found = ``true``; ` `                ``}  ` `                ``else`  `                ``{ ` `                    ``s.add(arr[j]); ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``if` `(found == ``false``) ` `        ``{ ` `            ``System.out.printf(````" No Triplet Found "````); ` `        ``} ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``int` `arr[] = {``0``, -``1``, ``2``, -``3``, ``1``}; ` `        ``int` `n = arr.length; ` `        ``findTriplets(arr, n); ` `    ``} ` `} ` ` `  `// This code contributed by Rajput-Ji `

## Python3

 `# Python3 program to find triplets  ` `# in a given array whose sum is zero  ` ` `  `# function to print triplets with 0 sum  ` `def` `findTriplets(arr, n): ` `    ``found ``=` `False` `    ``for` `i ``in` `range``(n ``-` `1``): ` ` `  `        ``# Find all pairs with sum  ` `        ``# equals to "-arr[i]"  ` `        ``s ``=` `set``() ` `        ``for` `j ``in` `range``(i ``+` `1``, n): ` `            ``x ``=` `-``(arr[i] ``+` `arr[j]) ` `            ``if` `x ``in` `s: ` `                ``print``(x, arr[i], arr[j]) ` `                ``found ``=` `True` `            ``else``: ` `                ``s.add(arr[j]) ` `    ``if` `found ``=``=` `False``: ` `        ``print``(``"No Triplet Found"``) ` ` `  `# Driver Code ` `arr ``=` `[``0``, ``-``1``, ``2``, ``-``3``, ``1``] ` `n ``=` `len``(arr) ` `findTriplets(arr, n) ` ` `  `# This code is contributed by Shrikant13 `

## C#

 `// C# program to find triplets in a given ` `// array whose sum is zero ` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `class` `GFG  ` `{ ` ` `  `    ``// function to print triplets with 0 sum ` `    ``static` `void` `findTriplets(``int` `[]arr, ``int` `n)  ` `    ``{ ` `        ``bool` `found = ``false``; ` ` `  `        ``for` `(``int` `i = 0; i < n - 1; i++)  ` `        ``{ ` `            ``// Find all pairs with sum equals to ` `            ``// "-arr[i]" ` `            ``HashSet<``int``> s = ``new` `HashSet<``int``>(); ` `            ``for` `(``int` `j = i + 1; j < n; j++)  ` `            ``{ ` `                ``int` `x = -(arr[i] + arr[j]); ` `                ``if` `(s.Contains(x))  ` `                ``{ ` `                    ``Console.Write(````"{0} {1} {2} "````, x, arr[i], arr[j]); ` `                    ``found = ``true``; ` `                ``}  ` `                ``else` `                ``{ ` `                    ``s.Add(arr[j]); ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``if` `(found == ``false``) ` `        ``{ ` `            ``Console.Write(````" No Triplet Found "````); ` `        ``} ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main(String[] args)  ` `    ``{ ` `        ``int` `[]arr = {0, -1, 2, -3, 1}; ` `        ``int` `n = arr.Length; ` `        ``findTriplets(arr, n); ` `    ``} ` `} ` ` `  `// This code has been contributed by 29AjayKumar `

Output:

```-1 0 1
-3 2 1
```

Time Complexity : O(n2)
Auxiliary Space : O(n)

Method 3 (Sorting : O(n2))
The above method requires extra space. We can solve in O(1) extra space. The idea is based on method 2 of this post.

```1. Sort all element of array
2. Run loop from i=0 to n-2.
Initialize two index variables l=i+1 and r=n-1
4. while (l < r)
Check sum of arr[i], arr[l], arr[r] is
zero or not if sum is zero then print the
triplet and do l++ and r--.
5. If sum is less than zero then l++
6. If sum is greater than zero then r--
```

## C++

 `// C++ program to find triplets in a given ` `// array whose sum is zero ` `#include ` `using` `namespace` `std; ` ` `  `// function to print triplets with 0 sum ` `void` `findTriplets(``int` `arr[], ``int` `n) ` `{ ` `    ``bool` `found = ``false``; ` ` `  `    ``// sort array elements ` `    ``sort(arr, arr+n); ` ` `  `    ``for` `(``int` `i=0; i

## Java

 `// Java  program to find triplets in a given ` `// array whose sum is zero ` `import` `java.util.Arrays;  ` `import` `java.io.*; ` ` `  `class` `GFG { ` `    ``// function to print triplets with 0 sum ` `static` `void` `findTriplets(``int` `arr[], ``int` `n) ` `{ ` `    ``boolean` `found = ``false``; ` ` `  `    ``// sort array elements ` `    ``Arrays.sort(arr); ` ` `  `    ``for` `(``int` `i=``0``; i

## Python3

 `# python program to find triplets in a given ` `# array whose sum is zero ` ` `  `# function to print triplets with 0 sum ` `def` `findTriplets(arr, n): ` ` `  `    ``found ``=` `False` ` `  `    ``# sort array elements ` `    ``arr.sort() ` ` `  `    ``for` `i ``in` `range``(``0``, n``-``1``): ` `     `  `        ``# initialize left and right ` `        ``l ``=` `i ``+` `1` `        ``r ``=` `n ``-` `1` `        ``x ``=` `arr[i] ` `        ``while` `(l < r): ` `         `  `            ``if` `(x ``+` `arr[l] ``+` `arr[r] ``=``=` `0``): ` `                ``# print elements if it's sum is zero ` `                ``print``(x, arr[l], arr[r]) ` `                ``l``+``=``1` `                ``r``-``=``1` `                ``found ``=` `True` `             `  ` `  `            ``# If sum of three elements is less ` `            ``# than zero then increment in left ` `            ``elif` `(x ``+` `arr[l] ``+` `arr[r] < ``0``): ` `                ``l``+``=``1` ` `  `            ``# if sum is greater than zero than ` `            ``# decrement in right side ` `            ``else``: ` `                ``r``-``=``1` `         `  `    ``if` `(found ``=``=` `False``): ` `        ``print``(``" No Triplet Found"``) ` ` `  ` `  `# Driven source ` `arr ``=` `[``0``, ``-``1``, ``2``, ``-``3``, ``1``] ` `n ``=` `len``(arr) ` `findTriplets(arr, n) ` ` `  `# This code is contributed by Smitha Dinesh Semwal `

## C#

 `// C#  program to find triplets in a given ` `// array whose sum is zero ` `using` `System; ` ` `  `public` `class` `GFG{ ` `        ``// function to print triplets with 0 sum ` `static` `void` `findTriplets(``int` `[]arr, ``int` `n) ` `{ ` `    ``bool` `found = ``false``; ` ` `  `    ``// sort array elements ` `    ``Array.Sort(arr); ` ` `  `    ``for` `(``int` `i=0; i

## PHP

 ` `

Output :

```-3 1 2
-1 0 1
```

Time Complexity : O(n2)
Auxiliary Space : O(1)