Skip to content

Instantly share code, notes, and snippets.

@ms1797

ms1797/kSum_recursive.cpp

Last active November 24, 2018 15:38
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ms1797/1074b032f0d637827e690dbaa3bee9fe to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ms1797/1074b032f0d637827e690dbaa3bee9fe to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. ms1797 revised this gist Nov 24, 2018. 1 changed file with 0 additions and 4 deletions.
    4 changes: 0 additions & 4 deletions kSum_recursive.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -1,7 +1,3 @@
    /*
    *?
    #include <bits/stdc++.h>
    using namespace std;

  2. ms1797 created this gist Nov 24, 2018.
    119 changes: 119 additions & 0 deletions kSum_recursive.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,119 @@
    /*
    *?
    #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;
    }