C++ generalized to kSum
Generalization to k-sum problems\n\nFor k >= 3, the following solution achieves the best time complexity possible which is O( n^{k-1} ).\nc++\n\tvoid kSum(vecto
# Generalization to k-sum problems\n\nFor `k >= 3`, the following solution achieves the best time complexity possible which is `O( n^{k-1} )`.\n```c++\n\tvoid kSum(vector<int>& nums, int target, int k, int start, vector<vector<int>>& res, vector<int>& curr, int sm){\n        if(k == 2){\n            int i = start, j = nums.size() - 1;\n            target -= sm;\n            while(i < j){\n                if(nums[i] + nums[j] < target) i++;\n                else if(nums[i] + nums[j] > target) j--;\n                else{\n                    curr[curr.size() - 2] = nums[i];\n                    curr[curr.size() - 1] = nums[j];\n                    res.push_back(curr);\n                    while(i + 1 < j && nums[i] == nums[i + 1]) i++;\n                    i++;\n                    while(i < j - 1 && nums[j] == nums[j - 1]) j--;\n                    j--;\n                }\n            }\n            return;\n        }\n        for(int i = start; i + k - 1 < nums.size(); i++){\n            curr[curr.size() - k] = nums[i];\n            kSum(nums, target, k - 1, i + 1, res, curr, sm + nums[i]);\n            while(i + 1 < nums.size() && nums[i] == nums[i + 1]) i++;\n        }\n    }\n    \n    inline vector<vector<int>> kSumWrapper(vector<int>& nums, int target, int k){\n        vector<vector<int>> res;\n        sort(nums.begin(), nums.end());\n        vector<int> curr(k, 0);\n        kSum(nums, target, k, 0, res, curr, 0);\n        return res;\n    }\n    \n    vector<vector<int>> fourSum(vector<int>& nums, int target) {\n        return kSumWrapper(nums, target, 4);\n    }\n```\n\n************************************************************************************************\n\nFor `k == 2`, the above solution does not achieve the best time complexity possible. One should instead use hash-table approach to achieve `O(n)` time complexity.
['C++']