4Sum C++ solution with explanation and comparison with 3Sum problem. Easy to understand.


  • 56
    K

    For the reference, please have a look at my explanation of 3Sum problem because the algorithm are exactly the same. The link is as blow.

    My 3Sum problem answer

    The key idea is to downgrade the problem to a 2Sum problem eventually. And the same algorithm can be expand to NSum problem.

    After you had a look at my explanation of 3Sum, the code below will be extremely easy to understand.

    class Solution {
    public:
        vector<vector<int> > fourSum(vector<int> &num, int target) {
        
            vector<vector<int> > res;
        
            if (num.empty())
                return res;
        
            std::sort(num.begin(),num.end());
        
            for (int i = 0; i < num.size(); i++) {
            
                int target_3 = target - num[i];
            
                for (int j = i + 1; j < num.size(); j++) {
                
                    int target_2 = target_3 - num[j];
                
                    int front = j + 1;
                    int back = num.size() - 1;
                
                    while(front < back) {
                    
                        int two_sum = num[front] + num[back];
                    
                        if (two_sum < target_2) front++;
                    
                        else if (two_sum > target_2) back--;
                    
                        else {
                        
                            vector<int> quadruplet(4, 0);
                            quadruplet[0] = num[i];
                            quadruplet[1] = num[j];
                            quadruplet[2] = num[front];
                            quadruplet[3] = num[back];
                            res.push_back(quadruplet);
                        
                            // Processing the duplicates of number 3
                            while (front < back && num[front] == quadruplet[2]) ++front;
                        
                            // Processing the duplicates of number 4
                            while (front < back && num[back] == quadruplet[3]) --back;
                    
                        }
                    }
                    
                    // Processing the duplicates of number 2
                    while(j + 1 < num.size() && num[j + 1] == num[j]) ++j;
                }
            
                // Processing the duplicates of number 1
                while (i + 1 < num.size() && num[i + 1] == num[i]) ++i;
            
            }
        
            return res;
        
        }
    };
    

  • 0
    S

    in the Nsum problem, your method will have N loops ........


  • 0
    K

    That's true. Nevertheless, I do remember that at somewhere I've read about the rigorous proof about this problem of which the result is bounded by O(m^n), where M is the size of the array and n is the same number as the n in n-th sum problem. Correct me if I'm wrong.


  • 0
    Z

    Is this O(nˆ3) runtime solution? it seems to be.


  • 0
    A

    yes it is cubic


  • 0
    N

    No actually it is bounded by O(m^n) where m is same as you stated but n is floor(n/2) in nth sum problem.


  • 0
    W

    @namangoyal, Could you show me the page where you see the conclusion? Thanks.


  • 2
    N

    num.empty() should be nums.size() < 4


  • 0
    N

    copy your solution with some changes

    class Solution {
    public:
        vector<vector<int> > fourSum(vector<int> &num, int target)
        {
            vector<vector<int> > res;
            if (num.size() < 4)
                return res;
            std::sort(num.begin(),num.end());
            int i, j;
            while (i < num.size() - 3)
            {
                j = i+1;
                while (j < num.size() - 2)
                {
                    int target_2 = target - num[i] - num[j];
                    int front = j + 1;
                    int back = num.size() - 1;
                    while(front < back) {
                        int two_sum = num[front] + num[back];
                        if (two_sum < target_2) front++;
                        else if (two_sum > target_2) back--;
                        else {
                            vector<int> quadruplet(4, 0);
                            quadruplet[0] = num[i];
                            quadruplet[1] = num[j];
                            quadruplet[2] = num[front];
                            quadruplet[3] = num[back];
                            res.push_back(quadruplet);
                            // Processing the duplicates of number 3
                            while (front < back && num[front] == quadruplet[2]) ++front;
                            // Processing the duplicates of number 4 
                            while (front < back && num[back] == quadruplet[3]) --back;
                        } } // Processing the duplicates of number 2 
                    while(j < num.size() - 2 && num[j + 1] == num[j++]);
                } // Processing the duplicates of number 1 
                while (i < num.size() - 3 && num[i + 1] == num[i++]);
            }
            return res;
        } 
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.