Two way Merge || C ++ ||  O(max(nlogn,  k^2))
\nclass Solution {\npublic:\n    typedef long long LL;\n    long long kSum(vector<int>& nums, int k) {\n        LL sum = 0;\n        vector<int> pos;\n        f
```\nclass Solution {\npublic:\n    typedef long long LL;\n    long long kSum(vector<int>& nums, int k) {\n        LL sum = 0;\n        vector<int> pos;\n        for(auto x : nums){\n            if(x > 0){\n                sum += x;\n                pos.push_back(-x);\n            }else{\n                pos.push_back(x);\n            }\n        }\n        sort(pos.begin(), pos.end(), greater<int>());\n        if(pos.size() > k) pos.erase(pos.begin() + k, pos.end());   //accelerate 1;\n        vector<LL> a(1, sum), b;\n        \n        for(auto x : pos){\n            b.clear();\n            int i = 0, j = 0, n = a.size(), m = min(k, n * 2), cnt = 0;\n            while(i < n && j < n && cnt < m){                       //accelerate 2;\n                if(a[i] > a[j] + x) b.push_back(a[i ++]), cnt ++;\n                else b.push_back(a[j ++] + x), cnt ++;\n            } \n            while(i < n && cnt < m) b.push_back(a[i ++]), cnt ++;\n            while(j < n && cnt < m) b.push_back(a[j ++] + x), cnt ++;\n            a = b; \n        }\n\n        return a[k - 1];\n    }\n};\n```
[]