O(nk) brute force solution
First of all, I didn\'t pass (TLE), but I saw someone passed using same brute-force approach with many tricks to optimize the constant https://leetcode.com/prob
First of all, I didn\'t pass (TLE), but I saw someone passed using same brute-force approach with many tricks to optimize the constant https://leetcode.com/problems/find-the-k-sum-of-an-array/discuss/2456909/O(n-*-klogk)-solution-%2B-clever-tricks, so I guess my solution is worth mentioning.\nThe idea is to keep only the top k sums as you iterate through the array, since if a sum is not in the top k at some moment, it will never be in top k in the end, so we can safely discard it.\n\nHere, I\'ll just show how to optimize the O(nk log k) solution to O(nk). Instead of using a set or sorted list, notice that if the maintained list is sorted, then nums[i] + the list is also sorted. Now, we can just merge the two different lists into one sorted list (like what we do in merge sort). I used `std::inplace_merge` in C++ to do this, but I guess it is still not fast enough.\n\n```cpp\nclass Solution {\npublic:\n    long long kSum(vector<int>& nums, int k) {\n        vector<long long> st;\n        st.push_back(0);\n        int n = nums.size();\n        for (int i = 0; i < n; i++) {\n            int m = st.size();\n            for (int j = 0; j < min(k, m); j++)\n                st.push_back(st[j] + (long long)nums[i]);\n            auto it = st.begin() + m;\n            inplace_merge(st.begin(), it, st.end(), greater<long long>());\n            if (st.size() > k)\n                st.resize(k);\n        }\n        return st[k-1];\n    }\n};\n```
[]