CareerCup

Loop through the array...for every item reduce the problem to classic "pairs with sum" problem and solve using HashMap. The time would be O(n^2).
E.g. [-1,-3,5,4]
for first item -1 find all the pairs with sum= (0-(-1)=1. which would be -3 and 4 (-3+4=1),so triplet will be -1,-3 and 4.

My decision on python:

def find_triples(numbers):
        res = []
        positions = []
        length = len(numbers)
        i = 0
        
        while i < length:
            j = 0
            while j < length:                
                if j == i:
                    j += 1
                    continue
                k = 0
                while k < length:
                    if k == i or k == j:                    
                        k += 1
                        continue
                    if sorted([i, j, k], key=int) not in positions:
                        first = numbers[i]
                        second = numbers[j]
                        third = numbers[k]
                        if int(first) + int(second) + int(third) == 0:
                            res.append([first, second, third])
                            positions.append(sorted([i, j, k], key=int))
                    k += 1
                j += 1
            i += 1
        return res

Iterate over the array and for each item reduce the problem to classic "pairs with sum" problem.
E.g. For [-1,-3,4,5] for first item -1 find all the pairs in remaining [-3,4,5] whose sum is 0-(-1) =1. You can use HashMap to find the pairs. The time eff. would be O(n^2).

it is 3 sum problem.
first of all, sort the array,
then for each array[i], it is our job to find two elements from array[i+1] to array[n-1] that their sum is 0.
then this question becomes 2sum problem.

if the array is unique the time complexity is O(n^2)
if the array has replicated elements, time complexity is O(n^2log(n))

int searchit(int *t, int v, int i, int size)
{
	int h=v%size;

	if(t[h]==v && h!=i)
		return h;
	int pos=(h+1)%size;
	int p=h-1;
	if(p<0)
		p=size;
	while(pos!=p)
	{
		if(t[pos]==v && pos!=i)
			return pos;
		pos=(pos+1)%size;
	}
	printf("\n");
	return -1;
}


void ContinousSubArraySumZero_LimitedCount(int a[], int n, int count)
{
	int *t=new int[n+1];

	memset(t,INT_MIN,sizeof(int)*(n+1));
	t[0]=0;
	int i,j,k;

	for(i=1;i<n+1;i++)
		t[i]=t[i-1]+a[i-1];
    for(i=0;i<n+1;i++)
	{
		if(t[i]<0)
			t[i]*=-1;
	}
	
	for(i=0;i<n+1;i++)
	{
		j=searchit(t,t[i],i,n+1);
		if(j!=-1 && j!=i && j>i && (j-i<=count))
		{
			for(k=i;k<j;k++)
				printf("%d\t",a[k]);
			printf("\n");
		}
	}
	delete [] t;
}

first we solve the classic subset sum problem,then we find the triplets subset..

Can be solved in O(n^2). Iterate the array (i = 0 to n) and for each (i) add each other element in the array (j = i to n)m and check if difference to form sum 0, exist in the hashtable(h). if not found in h, add that a[j] to h as key and value as j (position). Here is the code:

static void PrintTriplet_SumZero(int[] a)
        {
            int n = a.Length;
            for (int i = 0; i < n; i++)
            {                
                Hashtable h = new Hashtable();
                for (int j = i+1; j < n; j++)
                {
                    int x = 0 - a[i] - a[j];
                    if (h.ContainsKey(x)) // check if differencee to form "0" exist in hash table
                    {                       
                        Console.WriteLine("Triplet form 0 sum {0} {1} {2}",a[i],a[(int)h[x]],a[j]);
                    }
                    else
                    {
                        h.Add(a[j], j); // trick, save number a key, and position as value
                    }
                }
            }
        }

If the array does not contain duplicated numbers, The algorithm's time complexity is O(n^2)。
But if not, let's set the array {-3, -3, 0, 3}.
is the output:
-3, 0, 3
or:
-3, 0, 3 and -3, 0, 3?
should we print all the duplicated triplets?
If yes, I guess the problem is much more complex.
Some one can give the code?

void printTriplet(const int a[], int n)
{
    for( int x = 0; x < n ; x ++ )
    {
        for( int y = 0; y < n; y ++ )
        {
            result[x][y] = a[x] + a[y];
            processed[x][y] = false;
    }
    
    int[] sortedArray = sort( a, n );
    
    for( int x = 0; x < n ; x ++ )
    {
        for( int y = 0; y < n - x; y ++ )
        {
            if( processed[x][y] )
                continue;
                
            processed[x][y] = true;
            int itemToLook = 0 - result[x][y];
            bool found = binarySearch( sortedArray, n, itemToLook );
            if( found )
            {
                int z = search( a, n, itemToLook );
                processed[y][x] = true;
                processed[x][z] = true;
                processed[y][z] = true;
                processed[z][x] = true;
                processed[z][y] = true;
                print( a[x], a[y], itemToLook );
            }
        }
    }
}

static void ArrayTriplesNoDupe(int[] sequence)
        {
            HashSet<Tuple<int,int,int>> hs = new HashSet<Tuple<int,int,int>>();

            int executions = 0;
            for (int i = 0; i < sequence.Length - 2; i++)
            {
                for (int j = i + 1; j < sequence.Length - 1; j++)
                {
                    for (int k = j + 1; k <= sequence.Length - 1; k++)
                    {
                        Tuple<int,int,int> t = new Tuple<int,int,int>(sequence[i],sequence[j],sequence[k]);

                        if (hs.Contains(t))
                        {
                            Console.WriteLine("Collision: {0}", t.ToString());
                            continue;
                        }
                        executions++;
                        if ((sequence[i] + sequence[j] + sequence[k]) == 0)
                        {
                            hs.Add(t);
                            Console.WriteLine("{0},{1},{2}", sequence[i], sequence[j], sequence[k]);
                        }
                    }
                }
            }

            Console.WriteLine("Executions: {0}", executions);
        }

divide the array in 2 arrays A1,A2. +ve numbers and -ve numbers.
repeat the approach for both the arrays:
- for each element e in array A1, find two elements in A2 such that A2[i]+A2[j]+e = 0.

you can sort the arrays to make searching efficient

public class TripletSumToZero {

	public static void main(String[] args){
		int [] A={ 1, 3,0, -5, 2, 4, -9 , 7, 8, 5, -6, -7, 4, 2};
		int l= A.length;
		tripletSumZero(A, l);
	}
	
	static void tripletSumZero(int [] A, int l){
		
		for(int i=0; i<l; i++)
			for(int j=i+1; j<l-1; j++)
				for(int k=j+1; k<l-2; k++)
					if(A[i]+A[j]==-A[k])
						System.out.print("("+A[i]+" "+A[j]+" "+A[k]+") ");
	}
}

void printAllTriplesSummmedToZero(arr){
	
	for( i = 0; i < arr.size-2; i++ ){
		for( j = i+1; j < arr.size-1; j++ ){
			for( k = j+1; k < arr.size; k++ ){
				if( arr[i] + arr[j] + arr[k] == 0 ){
					println "${arr[i]} + ${arr[j]} + ${arr[k]} = 0"
				}				
			}
		}
	}
	
}

yup its working ...

This is the subset sum problem with minor modifications on:
1. Target = 0 hence the new target value that is passed to subsequent iterations should be changed to target + a[i] instead of target - a[i]. It allows handling the negative values.

2. We need to keep track of a counter variable. This variable is incremented every time a new value is added to the subset vector, and decremented for every value that is popped out.

You can solve this problem in O(n) by onsidering the following approach:
a. Take an array that contains the negative elements.
b. Take an array that will hold the sum of the negative values that will be a positive element in the array that is a triplet which sums up to 0.
c. Whenever we have tracked two negative elements track the sum till now in prev_sum that will hold the positive value in the array
Here is the code:

#include <stdio.h>
#include <conio.h>
#include <limits.h>
void findTriplet(int arr[],int n)
{
	int bin[1000]={0},trip[2],k=0,sum=0,i,j,count_trip=1;
	for(i=0;i<n;i++)
	{
		if(arr[i]<0&&count_trip<3)
		{
			sum=sum+(-1*arr[i]);
                       bin[sum]=1;
			count_trip++;
			trip[k]=arr[i];
			k=k+1;
		}
		if(count_trip==3&&bin[sum]==1)
		{
			printf(" Triplet exists ");
			printf(" %d %d %d ",trip[0],trip[1],sum);
			sum=0;
			trip[0]=trip[1]=INT_MAX;
			count_trip=1;
			k=0;
		}
		if(arr[i]>0)
		{
			bin[arr[i]]=1;
			if(count_trip==3&&bin[sum]==1)
			{
				printf(" Triplet exists ");
				printf(" %d %d %d ",trip[0],trip[1],sum);
				sum=0;
				trip[0]=trip[1]=INT_MAX;
				count_trip=1;
				k=0;
			}
		}
	}
}
int main()
{
	int arr[]={-1,4,-3,-5,11,-6};
	int n=sizeof(arr)/sizeof(arr[0]);
	findTriplet(arr,n);
}