[c++] priority queue with explanation on the required knowledge
The biggest hurdle is the knowledge of generating a complete set of subsequences of an array. Using [1, 2, 4] as an example, we start with the first element and
The biggest hurdle is the knowledge of generating a complete set of subsequences of an array. Using [1, 2, 4] as an example, we start with the first element and get only one subsequence **[1]** to start filling the subseq set **{[1]}**. Next we take **[1]** out and add two new subsequences back into the set:\n\na). by adding the element next to 1 and we will get **[1, 2]**;\nb). by replace 1 by the element next to 1 and we will get **[2]**.\n\nIf we repeat this process we get:\n\n**{[1]} => {[1, 2], [2]} => {[1, 2, 4], [1, 4], [2, 4], [4]}** <= Note in each step the number of subsequences that is generated is doubled.\n\nEventually the complete set of subsequences is:\n\n**{[1], [1, 2], [2], [1, 2, 4], [1, 4], [2, 4], [4] plus []}**\n\nWith this if we sort the absolute value of elements, and pre-calculate the max sum among all subsequences which is the sum of all positive elements, and add the "-elements" back to the max sum. We use priority_queue to always start with the larger max sum. We also sort the array to ensure that we first deduct from the max sum smaller elements. Once we obtain the k-max sum, we have our answer.\n\nPlease upvote if you think this explanation helps.\n\n```\nclass Solution {\npublic:\n    long long kSum(vector<int>& nums, int k) {\n        vector<long long> res;\n        priority_queue<pair<long long, int>> pq{};\n        long long maxSum = 0;\n        for (auto& n : nums) {\n            if (n > 0) maxSum += n;\n            else n = -n;\n        }\n        res.push_back(maxSum);\n        sort(nums.begin(), nums.end());\n        pq.push(make_pair(maxSum - nums[0], 0));\n        while (res.size() <= k) {\n            auto cur = pq.top();\n            pq.pop();\n            res.push_back(cur.first);\n            if (cur.second + 1 < nums.size()) {\n                pq.push(make_pair(cur.first - nums[cur.second + 1], cur.second + 1));\n                pq.push(make_pair(cur.first + nums[cur.second] - nums[cur.second + 1], cur.second + 1));\n            }\n        }\n        return res[k - 1];\n    }\n};\n
['C', 'Heap (Priority Queue)']