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 s = new HashSet();             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)