Find all triplets with zero sum

Last Updated : 31 Mar, 2023

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

Examples :

Input: arr[] = {0, -1, 2, -3, 1}
Output: (0 -1 1), (2 -3 1)
Explanation: The triplets with zero sum are 0 + -1 + 1 = 0 and 2 + -3 + 1 = 0

Input: arr[] = {1, -2, 1, 0, 5}
Output: 1 -2 1
Explanation: The triplets with zero sum is 1 + -2 + 1 = 0

Naive approach: Below is the idea to solve the problem

Run three loops and check one by one whether the sum of the three elements is zero or not. If the sum of three elements is zero then print elements otherwise print not found.

Follow the below steps to Implement the Idea:

Run three nested loops with loop counter i, j, k
The first loops will run from 0 to n-3 and second loop from i+1 to n-2 and the third loop from j+1 to b. The loop counter represents the three elements of the triplet.
Check if the sum of elements at i’th, j’th, k’th is equal to zero or not. If yes print the sum else continue.

Below is the implementation of the above approach:

C++

// A simple C++ program to find three elements
// whose sum is equal to zero
#include <bits/stdc++.h>
using namespace std;
 
// Prints all triplets in arr[] with 0 sum
void findTriplets(int arr[], int n)
{
    bool found = false;
    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) {
                    cout << arr[i] << " " << arr[j] << " "
                         << arr[k] << endl;
                    found = true;
                }
            }
        }
    }
 
    // If no triplet with 0 sum found in array
    if (found == false)
        cout << " not exist " << endl;
}
 
// Driver code
int main()
{
    int arr[] = { 0, -1, 2, -3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    findTriplets(arr, n);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

C

// A simple C program to find three elements
// whose sum is equal to zero
#include <stdbool.h>
#include <stdio.h>
 
// Prints all triplets in arr[] with 0 sum
void findTriplets(int arr[], int n)
{
    bool found = false;
    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) {
                    printf("%d %d %d\n", arr[i], arr[j],
                           arr[k]);
                    found = true;
                }
            }
        }
    }
 
    // If no triplet with 0 sum found in array
    if (found == false)
        printf(" not exist \n");
}
 
// Driver code
int main()
{
    int arr[] = { 0, -1, 2, -3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    findTriplets(arr, n);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// A simple Java program to find three elements
// whose sum is equal to zero
import java.io.*;
import java.util.*;
class num {
    // Prints all triplets in arr[] with 0 sum
    static void findTriplets(int[] arr, int n)
    {
        boolean found = false;
        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) {
                        System.out.println(arr[i] + " "
                                           + arr[j] + " "
                                           + arr[k]);
                        found = true;
                    }
                }
            }
        }
 
        // If no triplet with 0 sum found in array
        if (found == false)
            System.out.println(" not exist ");
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 0, -1, 2, -3, 1 };
        int n = arr.length;
        findTriplets(arr, n);
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

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 = False
    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

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 = false;
        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("\n");
                        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

<?php
// A simple PHP program to 
// find three elements whose 
// sum is equal to zero
 
// Prints all triplets
// in arr[] with 0 sum
function findTriplets($arr, $n)
{
    $found = false;
    for ($i = 0; $i < $n - 2; $i++)
    {
        for ($j = $i + 1; $j < $n - 1; $j++)
        {
            for ($k = $j + 1; $k < $n; $k++)
            {
                if ($arr[$i] + $arr[$j] + 
                               $arr[$k] == 0)
                {
                    echo $arr[$i] , " ",
                         $arr[$j] , " ",
                         $arr[$k] ,"\n";
                    $found = true;
                }
            }
        }
    }
 
    // If no triplet with 0
    // sum found in array
    if ($found == false)
        echo " not exist ", "\n";
 
}
 
// Driver Code
$arr = array (0, -1, 2, -3, 1);
$n = sizeof($arr);
findTriplets($arr, $n);
 
// This code is contributed by m_kit
?>

Javascript

<script>
// A simple Javascript program to find
//three elements whose sum is equal to zero
    arr = [0, -1, 2, -3, 1];
     
// Prints all triplets in arr[] with 0 sum    
    function findTriplets(arr) {
        let found = false;
        for (let i = 0; i < arr.length - 2; i++) {
        for (let j = i + 1; j < arr.length - 1; j++) {
            for (let k = j + 1; k < arr.length; k++) {
                if (arr[i] + arr[j] + arr[k] === 0)
                {
                    document.write(arr[i]);
                    document.write(" ");
                    document.write(arr[j]);
                    document.write(" ");
                    document.write(arr[k]);
                    document.write("<br>");
                    found = true;
                    
                }
            }
        }
        // If no triplet with 0 sum found in array
        if(found === false) {
            document.write(" not exist ");
        }
    }
   }
    findTriplets(arr);
// This code is contributed by Surbhi Tyagi
</script>

Output

0 -1 1
2 -3 1

Time Complexity: O(n³), As three nested loops are required, so the time complexity is O(n³).
Auxiliary Space: O(1), Since no extra space is required, so the space complexity is constant.

Find all triplets with zero sum using Hashing

Below is the idea to solve the problem

This involves traversing through the array. For every element arr[i], find a pair with sum “-arr[i]”. This problem reduces to pair sum and can be solved in O(n) time using hashing.

Follow the steps below to implement the idea:

Create a HashSet to store a unique element.
Run a nested loop with two loops, the outer loop from 0 to n-2 and the inner loop from i+1 to n-1
Check if the sum of ith and jth element multiplied with -1 is present in the HashSet or not
If the element is present in the HashSet, print the triplet else insert the jth element in the HashSet.

Below is the implementation of the above approach:

C++

// C++ program to find triplets in a given
// array whose sum is zero
#include <bits/stdc++.h>
using namespace std;
 
// function to print triplets with 0 sum
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]"
        unordered_set<int> s;
        for (int j = i + 1; j < n; j++) {
            int x = -(arr[i] + arr[j]);
            if (s.find(x) != s.end()) {
                printf("%d %d %d\n", x, arr[i], arr[j]);
                found = true;
            }
            else
                s.insert(arr[j]);
        }
    }
 
    if (found == false)
        cout << " No Triplet Found" << endl;
}
 
// Driver code
int main()
{
    int arr[] = { 0, -1, 2, -3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    findTriplets(arr, n);
    return 0;
}

Java

// Java program to find triplets in a given
// array whose sum is zero
import java.io.*;
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<Integer> s = new HashSet<Integer>();
            for (int j = i + 1; j < n; j++) {
                int x = -(arr[i] + arr[j]);
                if (s.contains(x)) {
                    System.out.printf("%d %d %d\n", x,
                                      arr[i], arr[j]);
                    found = true;
                }
                else {
                    s.add(arr[j]);
                }
            }
        }
 
        if (found == false) {
            System.out.printf(" No Triplet Found\n");
        }
    }
 
    // 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}\n", x,
                                  arr[i], arr[j]);
                    found = true;
                }
                else {
                    s.Add(arr[j]);
                }
            }
        }
 
        if (found == false) {
            Console.Write(" No Triplet Found\n");
        }
    }
 
    // 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

Javascript

<script>
  
// Javascript program to find triplets in a given
// array whose sum is zero
 
// function to print triplets with 0 sum
function findTriplets(arr, n)
{
    var found = false;
 
    for (var i = 0; i < n - 1; i++)
    {
        // Find all pairs with sum equals to
        // "-arr[i]"
        var s = new Set();
        for (var j = i + 1; j < n; j++)
        {
            var x = -(arr[i] + arr[j]);
            if (s.has(x))
            {
                document.write( x + " " + arr[i] + " " + arr[j] + "<br>");
                found = true;
            }
            else
                s.add(arr[j]);
        }
    }
 
    if (found == false)
        document.write( " No Triplet Found" );
}
 
// Driver code
var arr = [0, -1, 2, -3, 1];
var n = arr.length;
findTriplets(arr, n);
 
// This code is contributed by famously.
</script>

Output

-1 0 1
-3 2 1

Time Complexity: O(n²), Since two nested loops are required, so the time complexity is O(n²).
Auxiliary Space: O(n), Since a HashSet is required, so the space complexity is linear.

Find all triplets with zero sum using Sorting:

The idea is based on the above discussed approach using Hashmap of this post. For every element check that there is a pair whose sum is equal to the negative value of that element.

Follow the steps below to implement the idea:

Sort the array in ascending order.
Traverse the array from start to end.
For every index i, create two variables l = i + 1 and r = n – 1
Run a loop until l is less than r if the sum of array[i], array[l] and array[r] is equal to zero then print the triplet and break the loop
If the sum is less than zero then increment the value of l, by increasing the value of l the sum will increase as the array is sorted, so array[l+1] > array [l]
If the sum is greater than zero then decrement the value of r, by decreasing the value of r the sum will decrease as the array is sorted, so array[r-1] < array [r].

Below is the implementation of the above approach:

C++

// C++ program to find triplets in a given
// array whose sum is zero
#include <bits/stdc++.h>
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 < n - 1; i++) {
        // initialize left and right
        int l = i + 1;
        int r = n - 1;
        int x = arr[i];
        while (l < r) {
            if (x + arr[l] + arr[r] == 0) {
                // print elements if it's sum is zero
                printf("%d %d %d\n", x, arr[l], arr[r]);
                l++;
                r--;
                found = true;
                //   break;
            }
 
            // If sum of three elements is less
            // than zero then increment in left
            else if (x + arr[l] + arr[r] < 0)
                l++;
 
            // if sum is greater than zero then
            // decrement in right side
            else
                r--;
        }
    }
 
    if (found == false)
        cout << " No Triplet Found" << endl;
}
 
// Driven source
int main()
{
    int arr[] = { 0, -1, 2, -3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    findTriplets(arr, n);
    return 0;
}

Java

// Java  program to find triplets in a given
// array whose sum is zero
import java.io.*;
import java.util.Arrays;
 
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 < n - 1; i++) {
            // initialize left and right
            int l = i + 1;
            int r = n - 1;
            int x = arr[i];
            while (l < r) {
                if (x + arr[l] + arr[r] == 0) {
                    // print elements if it's sum is zero
                    System.out.print(x + " ");
                    System.out.print(arr[l] + " ");
                    System.out.println(arr[r] + " ");
 
                    l++;
                    r--;
                    found = true;
                }
 
                // If sum of three elements is less
                // than zero then increment in left
                else if (x + arr[l] + arr[r] < 0)
                    l++;
 
                // if sum is greater than zero then
                // decrement in right side
                else
                    r--;
            }
        }
 
        if (found == false)
            System.out.println(" No Triplet Found");
    }
 
    // Driven source
    public static void main(String[] args)
    {
 
        int arr[] = { 0, -1, 2, -3, 1 };
        int n = arr.length;
        findTriplets(arr, n);
    }
    // This code is contributed by Tushil..
}

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 then
            # 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 < n - 1; i++) {
            // initialize left and right
            int l = i + 1;
            int r = n - 1;
            int x = arr[i];
            while (l < r) {
                if (x + arr[l] + arr[r] == 0) {
                    // print elements if it's sum is zero
                    Console.Write(x + " ");
                    Console.Write(arr[l] + " ");
                    Console.WriteLine(arr[r] + " ");
 
                    l++;
                    r--;
                    found = true;
                }
 
                // If sum of three elements is less
                // than zero then increment in left
                else if (x + arr[l] + arr[r] < 0)
                    l++;
 
                // if sum is greater than zero then
                // decrement in right side
                else
                    r--;
            }
        }
 
        if (found == false)
            Console.WriteLine(" No Triplet Found");
    }
 
    // Driven source
    static public void Main()
    {
 
        int[] arr = { 0, -1, 2, -3, 1 };
        int n = arr.Length;
        findTriplets(arr, n);
    }
    // This code is contributed by akt_mit..
}

PHP

<?php
// PHP program to find 
// triplets in a given
// array whose sum is zero
 
// function to print 
// triplets with 0 sum
function findTriplets($arr, $n)
{
    $found = false;
 
    // sort array elements
    sort($arr);
 
    for ($i = 0; $i < $n - 1; $i++)
    {
        // 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
                echo $x," ", $arr[$l],
                        " ", $arr[$r], "\n";
                $l++;
                $r--;
                $found = true;
            }
 
            // If sum of three elements 
            // is less than zero then 
            // increment in left
            else if ($x + $arr[$l] + 
                          $arr[$r] < 0)
                $l++;
 
            // if sum is greater than 
            // zero then decrement
            // in right side
            else
                $r--;
        }
    }
 
    if ($found == false)
        echo " No Triplet Found" ,"\n";
}
 
// Driver Code
$arr = array (0, -1, 2, -3, 1);
$n = sizeof($arr);
findTriplets($arr, $n);
 
// This code is contributed by ajit
?>

Javascript

<script>
 
// Javascript program to find triplets in a given
// array whose sum is zero
 
// function to print triplets with 0 sum
function findTriplets(arr, n)
{
    let found = false;
 
    // sort array elements
    arr.sort((a, b) => a - b);
 
    for (let i=0; i<n-1; i++)
    {
        // initialize left and right
        let l = i + 1;
        let r = n - 1;
        let x = arr[i];
        while (l < r)
        {
            if (x + arr[l] + arr[r] == 0)
            {
                // print elements if it's sum is zero
                document.write(x + " ");
                document.write(arr[l]+ " ");
                document.write(arr[r]+ " " + "<br>");
                l++;
                r--;
                found = true;
            }
 
            // If sum of three elements is less
            // than zero then increment in left
            else if (x + arr[l] + arr[r] < 0)
                l++;
 
            // if sum is greater than zero then
            // decrement in right side
            else
                r--;
        }
    }
 
    if (found == false)
        document.write(" No Triplet Found" + "<br>");
}
 
// Driven source
 
    let arr = [0, -1, 2, -3, 1];
    let n = arr.length;
    findTriplets(arr, n);
 
 
// This code is contributed by Mayank Tyagi
 
</script>

Output

-3 1 2
-1 0 1

Time Complexity: O(n²), Only two nested loops are required, so the time complexity is O(n²).
Auxiliary Space: O(1), no extra space is required, so the space complexity is constant.

Suggest improvement

Given Array of size n and a number k, find all elements that appear more than n/k times

Find the element before which all the elements are smaller than it, and after which all are greater

Share your thoughts in the comments

Most Common Searching Algorithms

Other Searching Algorithms

Comparisons between Searching Algorithms

Library implementations of Searching algorithms

Easy problems on Searching algorithms

Medium problems on Searching algorithms

Hard problems on Searching algorithms

Most Common Searching Algorithms

Other Searching Algorithms

Comparisons between Searching Algorithms

Library implementations of Searching algorithms

Easy problems on Searching algorithms

Medium problems on Searching algorithms

Hard problems on Searching algorithms

Find all triplets with zero sum

C++

C

Java

Python3

C#

PHP

Javascript

Find all triplets with zero sum using Hashing

C++

Java

Python3

C#

Javascript

Find all triplets with zero sum using Sorting:

C++

Java

Python3

C#

PHP

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?