一.题目解析
读完题目后我们知道，该题就是让我们在子序列中求和，我们要在不同的子序列中排序找到第K大的和。何为子序列？
子序列就是在一个数组中抽出一些元素构成一个新的数组即可，不要求一定是连续的；
例如：数组【4，5，6】，子序列有【4】【5】【6】【】【4，5】【4，6】【5，6】【4，5，6】我们其实就可以发现，一个数组中有N个元素，那么每个元素都会面临着选或者不选两种情况，那么一共就有2的N次方个子序列。
二.思路解析
1.找到数组子序列的第K大和，那我们就先想到，最大的和是谁？
最大的和当然是所有的正整数相加得到的和。
那么第二大和呢？一定是最大的和减去一个最小的正数，或者加上一个最大的负数就可以得到了。
所以我们第一步一定要把所有正整数的和求出来，令其为sum1，然后我让所有数组中所有元素排列好大小顺序，只要我找到了数组中子序列加起来的第K小的和sum2，让sum1-sum2我就知道了第K大的序列和。
问题又来了，我怎么找到最小的正数或者最大的负数？我又怎么知道他们的第K小的子序列？
如上图中，我们会发现最小的正数所在的位置和最大的负数位置是不好确定的（找到数组中最小的正整数后，找到其下标，然后再往左找负数，往右找正数，还要比较，非常麻烦）。所以我们再次 看到上面红色的那句话那么第二大和呢？一定是最大的和减去一个最小的正数，或者加上一个最大的负数就可以得到了。我们会发现，减去一个正数或者加上一个负数，不都是减去一个数的绝对值吗？无非还是一个在子序列中选不选的问题。所以我们在求出SUM1后，可以让数组全都带上绝对值，然后再排列好。
long sum1 = 0L;
for (int &x : nums)
{
if (x >= 0)
{
sum1 += x;
}
else
{
x = -x;
}
}
sort(nums.begin(),nums.end());
例如上述例子，Sum1=24，我要找其第二大的序列和，也就是在新数组中找到第二小的序列和，第二小的序列号很明显是1。所以第二大的序列和就是23，实际意义是选了所有正整数后，再选了一个-1.
我要找第3大的序列和呢？ 也就是在新数组中找到第三小的序列和，很明显是2.所以第三大的序列和就是22，实际意义是选了所有正整数后，我再选一个-2，或者是除了正2以外，所有正整数我都选。 所以我们知道，绝对值数组排列后，找到其第K小的序列和sum2，就是在原数组中最大和sum1可以选择一些正数不选，也可以选择一些负数选上。
接下来我们又回到问题的核心，在这个绝对值数组中，找到其子序列第K小的和，top—K问题我们一般都是用堆来解决。
每个元素都可以选或者不选，那么我们如何不重不漏的列出所有的子序列呢？
参考这种方法
也就是构造一个优先级队列。这个队列中的元素类型是一个pair（long，int），pair.first是子序列的和，pair.second是选完下一个要添加或者替换的元素下标。
构造一个小顶堆，堆中大于当前节点的元素需要下沉，因此使用greater
priority_queue<pair<long, int>, vector<pair<long, int>>, greater<>> pq;堆中一定有的一个元素是全都不选的0
所以
pq.emplace(0, 0); // 空子序列找第K小子序列方法：
while (--k) {
auto [s, i] = pq.top();
pq.pop();
if (i < nums.size()) {
// 在子序列的末尾添加 nums[i]
pq.emplace(s + nums[i], i + 1); // 下一个添加/替换的元素下标为 i+1
if (i) { // 替换子序列的末尾元素为 nums[i]
pq.emplace(s + nums[i] - nums[i - 1], i + 1);
}
}
}
最终返回：
return sum1 - pq.top().first;三.最终代码：
class Solution {
public:
long long kSum(vector<int> &nums, int k) {
long sum1 = 0L;
for (int &x : nums) {
if (x >= 0) {
sum1 += x;
} else {
x = -x;
}
}
sort(nums.begin(),nums.end());
priority_queue<pair<long, int>, vector<pair<long, int>>, greater<>> pq;
pq.emplace(0, 0); // 空子序列
while (--k) {
auto [s, i] = pq.top();
pq.pop();
if (i < nums.size()) {
// 在子序列的末尾添加 nums[i]
pq.emplace(s + nums[i], i + 1); // 下一个添加/替换的元素下标为 i+1
if (i) { // 替换子序列的末尾元素为 nums[i]
pq.emplace(s + nums[i] - nums[i - 1], i + 1);
}
}
}
return sum1 - pq.top().first;
}
};
