CareerCup

We can do it in 2 sum problem taking every number subracting with the sum and then finding the 2 numbers from the rest of the array using 2 sum algo(taking hash)

This is my try.........
I think it will work for all combinations not only for 3........
If there is any mistakes, help me to rectify it.........
/*Given a array of numbers and a number N. Find out all combinations of 3 numbers in array whose sum is N.*/
#include<iostream.h>
#include<conio.h>

int n,a[20],N,s,b[20];

void find_comb(int i,int j,int sum)
{
sum+=a[i];
b[j]=a[i];

if((j==N-1)&&(sum==s))
{
cout<<"{";
for(int k=0;k<=j;k++)
cout<<b[k]<<",";
cout<<"\b},";
}
else if(sum<s)
{
for(i++;i<n;i++)
find_comb(i,j+1,sum);
}

}
void main()
{

clrscr();

cout<<"Enter the lenth of array ";
cin>>n;

cout<<"Enter the numbers......";
for(int i=0;i<n;i++)
{
cin>>a[i];
}

cout<<"Enter the Sum ";
cin>>s;

cout<<"Enter the Number of combinations ";
cin>>N;

for(i=0;i<n-N+1;i++)
find_comb(i,0,0);
cout<<"\b";

getch();

}

Here is the algorithm :
K is given number.

-sort the data A[1 to n] O(nlogn)
  for i = 1 to n
     apply finding two data problem whose sum is K-A[i]  and data set is all number except A[i] O(n)

here total time complexity goes to O(n*n)