Posted on by Kalkicode
Code Array

# Find all triplets with zero sum

The problem involves finding all unique triplets within a given array of integers whose sum is zero. This problem requires identifying combinations of three numbers that add up to zero.

## Problem Statement

Given an array of integers, find all unique triplets in the array that sum up to zero.

## Example

Consider the following array:

``arr = [8, 2, 0, 6, -2, 6, -1, 9, 4, 3]``

The unique triplets with zero sum are `[(2, 0, -2), (-2, -1, 3)]`.

## Idea to Solve

The algorithm involves iterating through the array and using three nested loops to find all possible combinations of triplets. For each triplet, the algorithm checks whether their sum is zero and prints the unique triplets.

## Pseudocode

``````function zero_sum_triplet(arr, size):
if size < 3:
return
Print "Array: "
Display array elements

Initialize status = 0

for i from 0 to size - 3:
for j from i + 1 to size - 2:
for k from j + 1 to size - 1:
if arr[i] + arr[j] + arr[k] == 0:
Print triplet (arr[i], arr[j], arr[k])
Set status = 1

if status == 0:
Print "None"``````

## Algorithm Explanation

1. The `zero_sum_triplet` function iterates through the array and uses three nested loops to generate all possible combinations of triplets.
2. If the sum of the triplet elements is zero, it prints the triplet and sets the `status` to 1.
3. After iterating through all possible triplets, the algorithm checks if any triplets were found. If no triplets were found, it prints "None."

## Code Solution

``````// C Program
// Find all triplets with zero sum
#include <stdio.h>

//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//Find all triplets in zero sum of given array
void zero_sum_triplet(int arr[], int size)
{
if (size < 3)
{
return;
}
printf("Array : ");
//Display array elements
display(arr, size);
//This variable are using to check zero sum exists or not
int status = 0;
//Loop which is iterate the first element of result
for (int i = 0; i < size - 2; ++i)
{
//Loop which is iterate the second element of result
for (int j = i + 1; j < size - 1; ++j)
{
//Loop which is iterate the third element of result
for (int k = j + 1; k < size; ++k)
{
//Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] == 0)
{
status = 1;
//Display three elements
printf("(%d,%d,%d) \n", arr[i], arr[j], arr[k]);
}
}
}
}
if (status == 0)
{
printf("None\n");
}
printf("\n");
}
int main()
{
//Define array elements
int arr1[] = {
8,
2,
0,
6,
-2,
6,
-1,
9,
4,
3
};
int size = sizeof(arr1) / sizeof(arr1[0]);
zero_sum_triplet(arr1, size);
//Define array elements
int arr2[] = {
9,
2,
-7,
4,
1,
3,
0,
7,
22,
8,
-4
};
size = sizeof(arr2) / sizeof(arr2[0]);
zero_sum_triplet(arr2, size);
return 0;
}``````

#### Output

``````Array : 8 2 0 6 -2 6 -1 9 4 3
(2,0,-2)
(-2,-1,3)

Array : 9 2 -7 4 1 3 0 7 22 8 -4
(-7,4,3)
(-7,0,7)
(4,0,-4)
(1,3,-4)
``````
``````/*
Java Program
Find all triplets with zero sum
*/
class MyArray
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i] + " ");
}
System.out.print("\n");
}
//Find all triplets in zero sum of given array
public void zero_sum_triplet(int[] arr, int size)
{
if (size < 3)
{
return;
}
System.out.print("Array : ");
//Display array elements
display(arr, size);
//This variable are using to check zero sum exists or not
boolean status = false;
//Loop which is iterate the first element of result
for (int i = 0; i < size - 2; ++i)
{
//Loop which is iterate the second element of result
for (int j = i + 1; j < size - 1; ++j)
{
//Loop which is iterate the third element of result
for (int k = j + 1; k < size; ++k)
{
//Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] == 0)
{
status = true;
//Display three elements
System.out.print("(" + arr[i] + "," + arr[j] + "," + arr[k] + ") \n");
}
}
}
}
if (status == false)
{
System.out.print("None\n");
}
System.out.print("\n");
}
public static void main(String[] args)
{
MyArray obj = new MyArray();
//Define array elements
int[] arr1 = {
8,
2,
0,
6,
-2,
6,
-1,
9,
4,
3
};
int size = arr1.length;
obj.zero_sum_triplet(arr1, size);
//Define array elements
int[] arr2 = {
9,
2,
-7,
4,
1,
3,
0,
7,
22,
8,
-4
};
size = arr2.length;
obj.zero_sum_triplet(arr2, size);
}
}``````

#### Output

``````Array :  8  2  0  6  -2  6  -1  9  4  3
(2,0,-2)
(-2,-1,3)

Array :  9  2  -7  4  1  3  0  7  22  8  -4
(-7,4,3)
(-7,0,7)
(4,0,-4)
(1,3,-4)
``````
``````/*
C++ Program
Find all triplets with zero sum
*/
#include<iostream>

using namespace std;
class MyArray
{
public:
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i] << " ";
}
cout << "\n";
}
//Find all triplets in zero sum of given array
void zero_sum_triplet(int arr[], int size)
{
if (size < 3)
{
return;
}
cout << "Array : ";
//Display array elements
this->display(arr, size);
//This variable are using to check zero sum exists or not
bool status = false;
//Loop which is iterate the first element of result
for (int i = 0; i < size - 2; ++i)
{
//Loop which is iterate the second element of result
for (int j = i + 1; j < size - 1; ++j)
{
//Loop which is iterate the third element of result
for (int k = j + 1; k < size; ++k)
{
//Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] == 0)
{
status = true;
cout << "(" << arr[i] << "," << arr[j] << "," << arr[k] << ") \n";
}
}
}
}
if (status == false)
{
cout << "None\n";
}
cout << "\n";
}
};
int main()
{
MyArray obj;
int arr1[] = {
8,
2,
0,
6,
-2,
6,
-1,
9,
4,
3
};
int size = sizeof(arr1) / sizeof(arr1[0]);
obj.zero_sum_triplet(arr1, size);
int arr2[] = {
9,
2,
-7,
4,
1,
3,
0,
7,
22,
8,
-4
};
size = sizeof(arr2) / sizeof(arr2[0]);
obj.zero_sum_triplet(arr2, size);
return 0;
}``````

#### Output

``````Array :  8  2  0  6  -2  6  -1  9  4  3
(2,0,-2)
(-2,-1,3)

Array :  9  2  -7  4  1  3  0  7  22  8  -4
(-7,4,3)
(-7,0,7)
(4,0,-4)
(1,3,-4)
``````
``````/*
C# Program
Find all triplets with zero sum
*/
using System;
class MyArray
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; i++)
{
Console.Write(" " + arr[i] + " ");
}
Console.Write("\n");
}
//Find all triplets in zero sum of given array
public void zero_sum_triplet(int[] arr, int size)
{
if (size < 3)
{
return;
}
Console.Write("Array : ");
//Display array elements
display(arr, size);
//This variable are using to check zero sum exists or not
Boolean status = false;
//Loop which is iterate the first element of result
for (int i = 0; i < size - 2; i++)
{
//Loop which is iterate the second element of result
for (int j = i + 1; j < size - 1; j++)
{
//Loop which is iterate the third element of result
for (int k = j + 1; k < size; k++)
{
//Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] == 0)
{
status = true;
Console.Write("(" + arr[i] + "," + arr[j] + "," + arr[k] + ") \n");
}
}
}
}
if (status == false)
{
Console.Write("None\n");
}
Console.Write("\n");
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();
int[] arr1 = {
8,
2,
0,
6,
-2,
6,
-1,
9,
4,
3
};
int size = arr1.Length;
obj.zero_sum_triplet(arr1, size);
int[] arr2 = {
9,
2,
-7,
4,
1,
3,
0,
7,
22,
8,
-4
};
size = arr2.Length;
obj.zero_sum_triplet(arr2, size);
}
}``````

#### Output

``````Array :  8  2  0  6  -2  6  -1  9  4  3
(2,0,-2)
(-2,-1,3)

Array :  9  2  -7  4  1  3  0  7  22  8  -4
(-7,4,3)
(-7,0,7)
(4,0,-4)
(1,3,-4)
``````
``````<?php
/*
Php Program
Find all triplets with zero sum
*/
class MyArray
{
//Function which is display array elements
function display( \$arr, \$size)
{
for (\$i = 0; \$i < \$size; ++\$i)
{
echo " ". \$arr[\$i] ." ";
}
echo "\n";
}
//Find all triplets in zero sum of given array
function zero_sum_triplet( \$arr, \$size)
{
if (\$size < 3)
{
return;
}
echo "Array : ";
//Display array elements
\$this->display(\$arr, \$size);
//This variable are using to check zero sum exists or not
\$status = false;
//Loop which is iterate the first element of result
for (\$i = 0; \$i < \$size - 2; ++\$i)
{
//Loop which is iterate the second element of result
for (\$j = \$i + 1; \$j < \$size - 1; ++\$j)
{
//Loop which is iterate the third element of result
for (\$k = \$j + 1; \$k < \$size; ++\$k)
{
//Check if whether resultant sum is to zero or not
if (\$arr[\$i] + \$arr[\$j] + \$arr[\$k] == 0)
{
\$status = true;
echo "(". \$arr[\$i] .",". \$arr[\$j] .",". \$arr[\$k] .") \n";
}
}
}
}
if (\$status == false)
{
echo "None\n";
}
echo "\n";
}
}

function main()
{
\$obj = new MyArray();
//Define array elements
\$arr1 = array(8, 2, 0, 6, -2, 6, -1, 9, 4, 3);
\$size = count(\$arr1);
\$obj->zero_sum_triplet(\$arr1, \$size);
//Define array elements
\$arr2 = array(9, 2, -7, 4, 1, 3, 0, 7, 22, 8, -4);
\$size = count(\$arr2);
\$obj->zero_sum_triplet(\$arr2, \$size);
}
main();``````

#### Output

``````Array :  8  2  0  6  -2  6  -1  9  4  3
(2,0,-2)
(-2,-1,3)

Array :  9  2  -7  4  1  3  0  7  22  8  -4
(-7,4,3)
(-7,0,7)
(4,0,-4)
(1,3,-4)
``````
``````#   Python 3 Program
#   Find all triplets with zero sum

class MyArray :
# Function which is display array elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i] ," ", end = "")
i += 1

print("\n", end = "")

# Find all triplets in zero sum of given array
def zero_sum_triplet(self, arr, size) :
if (size < 3) :
return

print("Array : ", end = "")
# Display array elements
self.display(arr, size)
# This variable are using to check zero sum exists or not
status = False
# Loop which is iterate the first element of result
i = 0
j = 0
k = 0
while (i < size - 2) :
# Loop which is iterate the second element of result
j = i + 1
while (j < size - 1) :
# Loop which is iterate the third element of result
k = j + 1
while (k < size) :
# Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] == 0) :
status = True
print("(", arr[i] ,",", arr[j] ,",", arr[k] ,") \n", end = "")

k += 1

j += 1

i += 1

if (status == False) :
print("None\n", end = "")

print("\n", end = "")

def main() :
obj = MyArray()
# Define array elements
arr1 = [8, 2, 0, 6, -2, 6, -1, 9, 4, 3]
size = len(arr1)
obj.zero_sum_triplet(arr1, size)
# Define array elements
arr2 = [9, 2, -7, 4, 1, 3, 0, 7, 22, 8, -4]
size = len(arr2)
obj.zero_sum_triplet(arr2, size)

if __name__ == "__main__": main()``````

#### Output

``````Array :   8    2    0    6    -2    6    -1    9    4    3
( 2 , 0 , -2 )
( -2 , -1 , 3 )

Array :   9    2    -7    4    1    3    0    7    22    8    -4
( -7 , 4 , 3 )
( -7 , 0 , 7 )
( 4 , 0 , -4 )
( 1 , 3 , -4 )
``````
``````#   Ruby Program
#   Find all triplets with zero sum

class MyArray

# Function which is display array elements
def display(arr, size)

i = 0
while (i < size)

print(" ", arr[i] ," ")
i += 1
end
print("\n")
end
# Find all triplets in zero sum of given array
def zero_sum_triplet(arr, size)

if (size < 3)

return
end
print("Array : ")
# Display array elements
self.display(arr, size)
# This variable are using to check zero sum exists or not
status = false
# Loop which is iterate the first element of result
i = 0
j = 0
k = 0
while (i < size - 2)

# Loop which is iterate the second element of result
j = i + 1
while (j < size - 1)

# Loop which is iterate the third element of result
k = j + 1
while (k < size)

# Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] == 0)

status = true
# Display three elements
print("(", arr[i] ,",", arr[j] ,",", arr[k] ,") \n")
end
k += 1
end
j += 1
end
i += 1
end
if (status == false)

print("None\n")
end
print("\n")
end
end
def main()

obj = MyArray.new()
# Define array elements
arr1 = [8, 2, 0, 6, -2, 6, -1, 9, 4, 3]
size = arr1.length
obj.zero_sum_triplet(arr1, size)
# Define array elements
arr2 = [9, 2, -7, 4, 1, 3, 0, 7, 22, 8, -4]
size = arr2.length
obj.zero_sum_triplet(arr2, size)
end
main()``````

#### Output

``````Array :  8  2  0  6  -2  6  -1  9  4  3
(2,0,-2)
(-2,-1,3)

Array :  9  2  -7  4  1  3  0  7  22  8  -4
(-7,4,3)
(-7,0,7)
(4,0,-4)
(1,3,-4)

``````
``````/*
Scala Program
Find all triplets with zero sum
*/
class MyArray
{
//Function which is display array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i) + " ");
i += 1;
}
print("\n");
}
//Find all triplets in zero sum of given array
def zero_sum_triplet(arr: Array[Int], size: Int): Unit = {
if (size < 3)
{
return;
}
print("Array : ");
//Display array elements
display(arr, size);
//This variable are using to check zero sum exists or not
var status: Boolean = false;
//Loop which is iterate the first element of result
var i: Int = 0;
var j: Int = 0;
var k: Int = 0;
while (i < size - 2)
{
//Loop which is iterate the second element of result
j = i + 1;
while (j < size - 1)
{
//Loop which is iterate the third element of result
k = j + 1;
while (k < size)
{
//Check if whether resultant sum is to zero or not
if (arr(i) + arr(j) + arr(k) == 0)
{
status = true;
//Display three elements
print("(" + arr(i) + "," + arr(j) + "," + arr(k) + ") \n");
}
k += 1;
}
j += 1;
}
i += 1;
}
if (status == false)
{
print("None\n");
}
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
//Define array elements
var arr1: Array[Int] = Array(8, 2, 0, 6, -2, 6, -1, 9, 4, 3);
var size: Int = arr1.length;
obj.zero_sum_triplet(arr1, size);
//Define array elements
var arr2: Array[Int] = Array(9, 2, -7, 4, 1, 3, 0, 7, 22, 8, -4);
size = arr2.length;
obj.zero_sum_triplet(arr2, size);
}
}``````

#### Output

``````Array :  8  2  0  6  -2  6  -1  9  4  3
(2,0,-2)
(-2,-1,3)

Array :  9  2  -7  4  1  3  0  7  22  8  -4
(-7,4,3)
(-7,0,7)
(4,0,-4)
(1,3,-4)
``````
``````/*
Swift Program
Find all triplets with zero sum
*/
class MyArray
{
//Function which is display array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i] ," ", terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Find all triplets in zero sum of given array
func zero_sum_triplet(_ arr: [Int], _ size: Int)
{
if (size < 3)
{
return;
}
print("Array : ", terminator: "");
//Display array elements
self.display(arr, size);
//This variable are using to check zero sum exists or not
var status: Bool = false;
//Loop which is iterate the first element of result
var i: Int = 0;
var j: Int = 0;
var k: Int = 0;
while (i < size - 2)
{
//Loop which is iterate the second element of result
j = i + 1;
while (j < size - 1)
{
//Loop which is iterate the third element of result
k = j + 1;
while (k < size)
{
//Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] == 0)
{
status = true;
print("(", arr[i] ,",", arr[j] ,",", arr[k] ,") \n", terminator: "");
}
k += 1;
}
j += 1;
}
i += 1;
}
if (status == false)
{
print("None\n", terminator: "");
}
print("\n", terminator: "");
}
}
func main()
{
let obj: MyArray = MyArray();
//Define array elements
let arr1: [Int] = [8, 2, 0, 6, -2, 6, -1, 9, 4, 3];
var size: Int = arr1.count;
obj.zero_sum_triplet(arr1, size);
//Define array elements
let arr2: [Int] = [9, 2, -7, 4, 1, 3, 0, 7, 22, 8, -4];
size = arr2.count;
obj.zero_sum_triplet(arr2, size);
}
main();``````

#### Output

``````Array :   8    2    0    6    -2    6    -1    9    4    3
( 2 , 0 , -2 )
( -2 , -1 , 3 )

Array :   9    2    -7    4    1    3    0    7    22    8    -4
( -7 , 4 , 3 )
( -7 , 0 , 7 )
( 4 , 0 , -4 )
( 1 , 3 , -4 )
``````
``````/*
Node Js Program
Find all triplets with zero sum
*/
class MyArray
{
//Function which is display array elements
display(arr, size)
{
var i = 0;
while (i < size)
{
process.stdout.write(" " + arr[i] + " ");
++i;
}
process.stdout.write("\n");
}
//Find all triplets in zero sum of given array
zero_sum_triplet(arr, size)
{
if (size < 3)
{
return;
}
process.stdout.write("Array : ");
//Display array elements
this.display(arr, size);
//This variable are using to check zero sum exists or not
var status = false;
//Loop which is iterate the first element of result
var i = 0;
var j = 0;
var k = 0;
while (i < size - 2)
{
//Loop which is iterate the second element of result
j = i + 1;
while (j < size - 1)
{
//Loop which is iterate the third element of result
k = j + 1;
while (k < size)
{
//Check if whether resultant sum is to zero or not
if (arr[i] + arr[j] + arr[k] == 0)
{
status = true;
process.stdout.write("(" + arr[i] + "," + arr[j] + "," + arr[k] + ") \n");
}
++k;
}
++j;
}
++i;
}
if (status == false)
{
process.stdout.write("None\n");
}
process.stdout.write("\n");
}
}

function main()
{
var obj = new MyArray();
//Define array elements
var arr1 = [8, 2, 0, 6, -2, 6, -1, 9, 4, 3];
var size = arr1.length;
obj.zero_sum_triplet(arr1, size);
//Define array elements
var arr2 = [9, 2, -7, 4, 1, 3, 0, 7, 22, 8, -4];
size = arr2.length;
obj.zero_sum_triplet(arr2, size);
}
main();``````

#### Output

``````Array :  8  2  0  6  -2  6  -1  9  4  3
(2,0,-2)
(-2,-1,3)

Array :  9  2  -7  4  1  3  0  7  22  8  -4
(-7,4,3)
(-7,0,7)
(4,0,-4)
(1,3,-4)
``````

## Time Complexity

The algorithm involves three nested loops, so the time complexity is cubic, `O(n^3)`, where `n` is the size of the array.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post