Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = 0.

Question

Please help me to find out such algorithm?

Comments

Its a combination of two problems one sorting the array and finding the pair(s) which has a sum say s.
1. Sort the array
2. For each element x find a pair in rest of the elements whose sum is -x.

and you are done but really interesting and difficult problem.

Answer 1

#include<iostream>
using namespace std;

void printAllSubset(int are[], int aux[], int size, int sum, int i, int j, int r)
{
     if(j == r && sum == 0)
     {
          for(int p =0; p<j; p++)
          {
             cout<<aux[p];
          }
          cout<<endl;
          return;
     }

     for(int q=0; q<n; q++)
     {
          aux[j] = arr[q];
          printAllSubset(arr, aux, n, sum+aux[j], q+1, j+1, r);
     }
}

int main()
{
  int arr[]={2,3,-5,1,-3, 0, 4,-1};
  int aux[3] ={0};
  int size = sizeof(arr)/sizeof(arr[0]);
  Int sum=0;
  printAllSubset(arr, aux, size, sum, 0, 0, 3);
  return 0;
}

Comments

I think the complexity here would be o(n^4), am I right??

---

Sir I think... complexity wud be exponential o(3^n).