quickselect + bruteforce
\n# Complexity\n- Time complexity: O(N + K^2)\n\n- Space complexity: O(N)\n\n# Code\n\nclass Solution {\npublic:\n    long long kSum(vector<int>& nums, int k) {
\n# Complexity\n- Time complexity: O(N + K^2)\n\n- Space complexity: O(N)\n\n# Code\n```\nclass Solution {\npublic:\n    long long kSum(vector<int>& nums, int k) {\n       vector<int> nonneg;\n       vector<int> neg;\n       vector<int> effect;\n       for(auto i: nums) {\n        if(i>=0) nonneg.push_back(i);\n        else neg.push_back(-i);\n       }\n       if(neg.size()>2*k) {\n         nth_element(neg.begin(), neg.begin()+2*k, neg.end());\n         for(int i = 0; i<2*k; ++i) effect.push_back(-neg[i]);\n       }else{\n        for (auto i: neg) effect.push_back(-i); \n       }\n\n       long ans = 0;\n       if(nonneg.size()>2*k) {\n         nth_element(nonneg.begin(), nonneg.begin()+2*k, nonneg.end());\n         for(int i = 0; i<2*k; ++i) effect.push_back(nonneg[i]);\n         for(int i = 2*k; i<nonneg.size(); ++i) ans+= nonneg[i];\n       \n       }else{\n        for (auto i: nonneg) effect.push_back(i);\n       }\n\n\n       long long* state = new long long[2*k];\n        state[0] = 0;\n        int count = 1;\n        for(auto v: effect) {\n            for(int i = 0; i<count; ++i) \n                 state[i+count] = state[i] - v;\n            count*=2;\n            if(count > k) {\n                std::nth_element(state, state + k - 1, state + count);\n                count = k;\n           }  \n        }\n        std::nth_element(state, state+k-1, state+count);\n        return ans - state[k-1];\n\n    }\n};\n```
['Quickselect', 'C++']