4Sum C++ solution with explanation and comparison with 3Sum problem. Easy to understand.
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.\n\n[My 3Sum problem ans
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.\n\n[My 3Sum problem answer][1]\n\nThe key idea is to downgrade the problem to a `2Sum` problem eventually. And the same algorithm can be expand to `NSum` problem.\n\nAfter you had a look at my explanation of `3Sum`, the code below will be extremely easy to understand.\n\n\n    class Solution {\n    public:\n        vector<vector<int> > fourSum(vector<int> &num, int target) {\n        \n            vector<vector<int> > res;\n        \n            if (num.empty())\n                return res;\n        \n            std::sort(num.begin(),num.end());\n        \n            for (int i = 0; i < num.size(); i++) {\n            \n                int target_3 = target - num[i];\n            \n                for (int j = i + 1; j < num.size(); j++) {\n                \n                    int target_2 = target_3 - num[j];\n                \n                    int front = j + 1;\n                    int back = num.size() - 1;\n                \n                    while(front < back) {\n                    \n                        int two_sum = num[front] + num[back];\n                    \n                        if (two_sum < target_2) front++;\n                    \n                        else if (two_sum > target_2) back--;\n                    \n                        else {\n                        \n                            vector<int> quadruplet(4, 0);\n                            quadruplet[0] = num[i];\n                            quadruplet[1] = num[j];\n                            quadruplet[2] = num[front];\n                            quadruplet[3] = num[back];\n                            res.push_back(quadruplet);\n                        \n                            // Processing the duplicates of number 3\n                            while (front < back && num[front] == quadruplet[2]) ++front;\n                        \n                            // Processing the duplicates of number 4\n                            while (front < back && num[back] == quadruplet[3]) --back;\n                    \n                        }\n                    }\n                    \n                    // Processing the duplicates of number 2\n                    while(j + 1 < num.size() && num[j + 1] == num[j]) ++j;\n                }\n            \n                // Processing the duplicates of number 1\n                while (i + 1 < num.size() && num[i + 1] == num[i]) ++i;\n            \n            }\n        \n            return res;\n        \n        }\n    };\n\n\n  [1]: https://oj.leetcode.com/discuss/23595/share-my-solution-around-50ms-with-explanation-and-comments
['C++']