find all unique triplet in given array with sum zero

[prasad123]

Hello to all of you...
I got all unique triplet from below code but I want to reduce its time complexity.
It consist three for loop. So my question is, Is it possible to do in minimum loop that it decrease its time complexity. code will be execute in minimum time.
Thanks in advanced let me know.

#include <cstdlib>
#include<iostream>
using namespace std;
void Triplet(int[], int, int); 
void Triplet(int array[], int n, int sum)
{
   // Fix the first element and find other two
     for (int i = 0; i < n-2; i++)
     {
        // Fix the second element and find one
 	       for (int j = i+1; j < n-1; j++)
        {
           // Fix the third element
           for (int k = j+1; k < n; k++)
           if (array[i] + array[j] + array[k] == sum)
            cout << "Result :\t" << array[i] << " + " << array[j] << " + " << array[k]<<" = " << sum << endl;
         }
      }
 }

int main()
{
    int A[] = {-10,-20,30,-5,25,15,-2,12};
    int sum = 0;
    int arr_size = sizeof(A)/sizeof(A[0]);
    cout<<"********************O(N^3) Time Complexity*****************************"<<endl;
    Triplet(A,arr_size,sum);
    return 0;
}

[MiiNiPaa]

If it is possible to change your array, there is obvious fix for your algorithm: sort array first , then search for triplets. You already know what third value should be if you know first two, so you can just test for its existence in array by binary search. O(N^2 logN)

Also you can apply some knowledge on resulting triplet: for example that there should be both negative and positive value here, so you can choose first two values to be of different signs. This will not reduce complexivity, but will improve execution time.

[JLBorges]

the algorithm below first sorts the input array and then tests all possible pairs in a careful order that avoids the need to binary search for the pairs in the sorted list, achieving worst-case O(n^2) time
https://en.wikipedia.org/wiki/3SUM#Quadratic_algorithm

[prasad123]

Thank you so muxh thanx to all.. i ll try with this and get back to you..

[prasad123]

@Miinipaa:- Actually I have already tried with your solution but it will give only two pairs not all unique pair.

[prasad123]

@JLBorges:-
Hi , i hav tried your soltuion but it still give only two triplet.I want all unique triplet so what should i do.? please let me know.

[JLBorges]

#include <iostream>
#include <vector>
#include <tuple>
#include <set>
#include <algorithm>

std::set< std::tuple<int,int,int> > unique_zero_3sum_tuples( std::vector<int> seq )
{
    std::set< std::tuple<int,int,int> > tuples ;

    const int n = seq.size() ;
    if( n > 2 )
    {
        sort( seq.begin(), seq.end() ) ;
        const int end = n - 2 ;

        for( int first = 0 ; first < end && seq[first] < 1 ; ++first )
        {

            int second = first + 1 ;
            int third = end + 1 ;

            while( second < third )
            {
                int sum = seq[first] + seq[second] + seq[third] ;

                if( sum == 0)
                {
                    tuples.insert( std::make_tuple( seq[first], seq[second], seq[third] ) ) ;
                    ++second ;
                    --third ;
                }

                else if( sum > 0 ) --third ;

                else ++second ; // sum < 0
            }
        }
    }

    return tuples ;
}

void print_unique_zero_3sum_triplets( std::vector<int> seq )
{
    for( const auto& tup : unique_zero_3sum_tuples(seq) )
        std::cout << std::get<0>(tup) << ' ' << std::get<1>(tup) << ' ' << std::get<2>(tup) << '\n' ;
}

int main()
{
    print_unique_zero_3sum_triplets( { -10, -10, -20, -20, 30, 30, -5, 25, 15, 15, -2, 12, 12 } ) ;
    std::cout << "------------------------\n" ;
    print_unique_zero_3sum_triplets( { -25, -10, -7, -3, 1, 2, 3, 4, 5, 8, 10, 13, 15, 17, 28, -10, -7, -3, 1, 2 } ) ;
}

http://coliru.stacked-crooked.com/a/95f631e92edcba36

[prasad123]

Thanx JLBorges.. I ll go with it.