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.

New Comment