given an array of integers in unsorted order , find all the unique set of k elements that sum to a given target. (k>=2)

kSum_recursive.cpp

#include <bits/stdc++.h>
using namespace std;

void display_vector(vector<int> &arr )
{
    for(int i = 0 ; i<arr.size() ; i++)
        {
            cout<<arr[i]<<" " ;
        }
        cout<<"\n" ;
}

void display_vectorOfPair(vector<pair<int, int > > &arr )
{
    for(int i = 0 ; i<arr.size() ; i++)
        {
            cout<<arr[i].first<<" "<<arr[i].second ;
            cout<<"\n" ;
        }
        cout<<"\n \n \n " ;

}
void display_vectorOfVector(vector<vector<int> > &arr )
{
    for(int i = 0 ; i<arr.size() ; i++)
    {
        for(int j = 0 ; j<arr[i].size() ; j++)
        {
            cout<<arr[i][j]<<" " ;
        }
        cout<<"\n" ;
    }

}

void kSum_helper(vector<vector<int> > &ans ,vector<int> &step ,vector<int> &A ,
                 int tempSum , int target , int k , int start)
{
    //cout<<"display step vector \n" ; display_vector(step) ;
    //cout<<"display ans vector \n" ; display_vectorOfVector(ans) ;
    //base case
    if(k == 2)
    {
        int l = start;
        int r = A.size() - 1 ;

        while(l < r)
        {
            int sum = tempSum + A[l] + A[r] ;
            if(sum < target )
                l++ ;
            else if(sum > target)
                r-- ;
            else
            {
                step.push_back(A[l]) ;
                step.push_back(A[r]) ;
                ans.push_back(step) ;
                step.pop_back() ;
                step.pop_back() ;

                l++ ;
                r-- ;

                while( l<r && A[l] == A[l-1])
                    l++;
                while( l<r && A[r] == A[r+1])
                    r-- ;
            }
        }
        return ;
    }

    if(A.size() - start < k)
        return  ;

    //recursive case
    for(int i = start ; i <= A.size() - k ; i++)
    {
        if( i > start && A[i] == A[i-1]) continue ;

        tempSum += A[i] ;       //cout<< "display tempSum : "<<tempSum <<"\n" ;
        step.push_back(A[i]) ;  //cout<< "display step vector\n" ; display_vector(step) ;
        kSum_helper(ans ,step , A ,tempSum , target , k-1 , i+1) ;
        tempSum -= A[i] ;
        step.pop_back() ;
     }
}

vector<vector<int> > kSum(vector<int> &A , int k ,int target)
{
    vector<vector<int> > ans ;
    vector<int> step ;
    int tempSum = 0 , start = 0 ;

    if(k<2)
        return ans ;
    //cout<<"display vector A \n" ;display_vector(A) ;
    sort(A.begin() , A.end()) ;
    //cout<<"display vector A \n" ;display_vector(A) ;
    kSum_helper(ans , step , A , tempSum , target , k , start ) ;

    return ans ;
}

int main()
{
    vector<int> A = {1, 0 , -1 ,0 , -2, 2};
    int target = 0 ;
    int k = 4 ;
    vector<vector<int> > ans = kSum(A , k , target) ;
    cout<<"output of program==> \n" ;
    display_vectorOfVector(ans) ;
    return 0;
}