Skip to content

Files

Latest commit

 

History

History
95 lines (71 loc) · 2.34 KB

22.md

File metadata and controls

95 lines (71 loc) · 2.34 KB

Recursion (TLE)

void findd( vector<vector<int>> &ans,int i,int sum,vector<int> &arr, int k,vector<int>v)
    {
        if(v.size()==4 && sum==k)
        {
            if( find(ans.begin(),ans.end(),v) == ans.end() )
                ans.push_back(v);
            return;
        }
        
        if(i==arr.size())
            return;
        
        v.push_back(arr[i]);
        findd(ans,i+1,sum+arr[i],arr,k,v);
        
        v.pop_back();
        findd(ans,i+1,sum,arr,k,v);
        
        
    }
    vector<vector<int> > fourSum(vector<int> &arr, int k) {
        // Your code goes here
        vector<int>v;
        sort(arr.begin(),arr.end());
        vector<vector<int>> ans;
        
        findd(ans,0,0,arr,k,v);
        return ans;
    }

Method 2

 vector<vector<int> > fourSum(vector<int> &arr, int k) {
        // Your code goes here
        
        vector<vector<int> > ans;
       
        sort(arr.begin(),arr.end());
        int n=arr.size();
        int sum=0;
        
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                int lo=j+1,hi=n-1;
                
                while(lo<hi)
                {
                    sum = arr[i] + arr[j] + arr[lo] +arr[hi];
                    if(sum<k)
                        lo++;
                        
                     else if(sum>k)
                        hi--;
                    
                    else
                    {
                         vector<int> v;
        
                        v.push_back(arr[i]);
                        v.push_back(arr[j]);
                        v.push_back(arr[lo]);
                        v.push_back(arr[hi]);
                        
                        lo++;
                        hi--;
                       // if(find(ans.begin(),ans.end(),v)==ans.end())            // this will give TLE
                             ans.push_back(v);
                    }
                    
                }
            }
        }
        
        set<vector<int>>s;
        for(auto &vec :ans)
            s.insert(vec);
            
        vector<vector<int>>ans1;
        for(auto vec:s)
            ans1.push_back(vec);
        
        return ans1;
    }