[Detailed Explanation & Cpp Code] Greedy Counting + Time O(N*log(N)+K*log(K)) + Space O(K)
\n//Document History\n//2022/08/21         Created\n//2022/08/22         Updated: Fix Typos, Edit Typeset\n//2022/08/23.        Updated: Add Figure to show the 
```\n//Document History\n//2022/08/21         Created\n//2022/08/22         Updated: Fix Typos, Edit Typeset\n//2022/08/23.        Updated: Add Figure to show the greedy approach of exploring \n```\n\n**The Problem**\nThe "**subsequence**" in the description is misleading. Actually, the order should be ignored.  The problem can be described as: ***Given N numbers, we want to find the Kth-Largest Sum of any subset of the numbers (empty set included).***\n\n**The Algorithm**\n**Step 1: Preprocess & 1st-Largetest Sum**\nWe do the following things at the very beginning.\n* **Calculate Sum of Positive Numbers**\n We pick all positive numbers and calculate the **SUM**. As you all know, this is the 1-Sum or 1st-largest sum.\n* **Multiple -1 for Negative Numbers**\nTo make the discussion simple, we multiple every negative number by -1.\n* **Sort the Numbers**\nWe sort the numbers and prepare for our **greedy strategy.**\n\nThe new problem becomes:***Given N non-negative numbers, we want to find the Kth-Smallest Sum of any subset of the numbers (empty set included).***\n\n**Step 2: Repeatly find the subset of the numbers with smallest sum**\nWe maintain a buffer of subsets. Repeatly, we pick the  subset whose sum is smallest from the buffer and explore **at most two** new subsets. For your information, we cannot afford to store the subset. We store the sum of the subset instead, as you can guess. Besides, we store information about the next element to visit. Finally, we employ a greedy strategy as following: \n*  We keep tracking **(running sum, next element to visit)** \n*  Given a subset, we explore two more subset\n\t*  the size of the subset is keep unchanged but replace the largest element with the **next element**.\n\t*  increase the size of subset by 1 to include the **next element**.\n\nAccording to the request of @xiaominglu, we show the greedy strategy with **Example 1: [1,2,3,4]**. We show all subset as nodes. Beginning with **[1]**, we explore at most two new subsets. At any time, every un-explored subset will bigger than one subset in the buffer (w.r.t. the sum of elements). In other words, the buffer is the **greedy frontier**. Furthermore, we guarantee that there will be **one and only one path** from the root (a.k.. empty set) to any node. As a result, we don\'t need to track nodes visited.\n![image](https://assets.leetcode.com/users/images/0ff3cc8d-eec3-41e6-bff7-adb77f4dba1c_1661256583.1306322.jpeg)\n![image](https://assets.leetcode.com/users/images/2cc6d7f8-2f06-49a6-8b56-825df13b11e2_1661256584.5121393.jpeg)\n\n\n\nWe use a MIN-heap to buffer the subset. Let\'s show what we can do with the aforementioned exmaple. For clarity, we show the candidate subset as well as the note. Please remember that we just keep record of limited information, a.k.a. **notes**, in the code.\n\nIn the following, we show our algorithm with  **Example 2: [1,-2,3,4,-10,12]**\nNow, we have **SUM**=20, and the numbers are sorted **[1,2,3,4,10,12]**. For clarity, let **S** be a subset of the numbers, and **Sum(S)** be the sum of the subset. **SUM-Sum(S)** will be the sum of a corresponding subset of the original numbers. \n\n\n\n* **Step 2.1  | 1-Sum=20-0**\nInital the buffer w.r.t. **[1,2,3,4,10,12]**\nBuffer Subset: **[1]**\nSubset Notes:   **(1,1),** \n* **Step 2.2  | 2-Sum=20-1**\nSubset Removed: **[1]**\nSubset Explored:  **[2], [1,2]**  \nBuffer Subset:  **[2],      [1,2]**\nSubset Notes:    **(2,2), (3,2)**\n* **Step 2.3 | 3-Sum=20-2**\nSubset Removed: **[2]**\nSubset Explored:  **[3], [2,3]**  \nBuffer Subset:  **[1,2],  [3],     [2,3]**\nSubset Notes:    **(3,2), (3,3), (5,3)**\n* **Step 2.4 | 4-Sum=20-3**\nSubset Removed: **[1,2]**\nSubset Explored:  **[1,3], [1,2,3]**  \nBuffer Subset:  **[3],      [2,3],  [1,3],  [1,2,3]**\nSubset Notes:    **(3,3), (5,3), (4,3), (6,3)**\n* **Step 2.5 | 5-Sum=20-3**\nSubset Removed: **[3]**\nSubset Explored:  **[4], [3,4]**  \nBuffer Subset:  **[2,3],  [1,3],  [1,2,3],[4],     [3,4]**\nSubsetNotes:    **(5,3), (4,3), (6,3),    (4,4),(7,4)**\n* **Step 2.6 | 6-Sum=20-4**\nSubset Removed: **[1,3]**\nSubset Explored:  **[1,4], [1,3,4]**  \nBuffer Subset:  **[2,3], [1,2,3], [4],      [3,4], [1,4], [1,3,4]**\nSubset Notes:    **(5,3),(6,3),    (4,4),  (7,4),(5,4), (8,4)**\n* **Step 2.7 | 7-Sum=20-4**\nSubset Removed: **[4]**\nSubset Explored:  **[10], [4,10]**  \nBuffer Subset:  **[2,3], [1,2,3], [3,4], [1,4], [1,3,4], [10],    [4,10]**\nSubset Notes:    **(5,3),(6,3),    (7,4), [5,4], (8,4),    (10,5),(14,5)**\n* **Step 2.8 |  8-Sum=20-5**\nSubset Removed: **[2,3]**\nSubset Explored:  **[2,4], [2,3,4]**  \nBuffer Subset:  **[1,2,3], [3,4], [1,4],  [1,3,4],[10],     [4,10], [2,4], [2,3,4]**\nSubset Notes:    **(6,3),    (7,4), [5,4], (8,4),    (10,5), (14,5),(6,4),(9,4)**\n* **Step 2.9 | 9-Sum=20-5**\nSubset Removed: **[1,4]**\nSubset Explored:  **[1,10], [1,4,10]**  \nBuffer Subset:  **[1,2,3], [3,4],  [1,3,4],[10],     [4,10], [2,4],  [2,3,4],[1,10], [1,4,10]**\nSubset Notes:    **(6,3),    (7,4), (8,4),    (10,5),(14,5), (6,4), (9,4),    (11,5), (15,5)**\n* **Step 2.10 | 10-Sum=20-6**\nSubset Removed: **[1,2,3]**\nSubset Explored:  **[1,2,4], [1,2,3,4]**  \nBuffer Subset:  **[3,4],  [1,3,4],[10],     [4,10], [2,4],  [2,3,4],[1,10], [1,4,10], [1,2,4], [1,2,3,4]**\nSubset Notes:    **(7,4), (8,4),    (10,5),(14,5), (6,4), (9,4),    (11,5), (15,5) (7,4), (10,4)**\n* **Step 2.11 | 11-Sum=20-6**\nSubset Removed: **[2,4]**\nSubset Explored:  **[2,10], [2,4,10]**  \nBuffer Subset:  **[3,4], [1,3,4],[10],    [4,10], [2,3,4],[1,10], [1,4,10],[1,2,4], [1,2,3,4],[2,10], [2,4,10]**\nSubset Notes:    **(7,4),(8,4),   (10,5),(14,5),(9,4),    (11,5),(15,5),    (7,4),    (10,4),     (12,5),(16,5)**\n* **Step 2.12 | 12-Sum=20-7**\nSubset Removed: **[3,4]**\nSubset Explored:  **[3,10], [3,4,10]**  \nBuffer Subset:  **[1,3,4],[10],    [4,10], [2,3,4],[1,10], [1,4,10],[1,2,4], [1,2,3,4],[2,10], [2,4,10],[3,10], [3,4,10]**\nSubset Notes:    **(8,4),   (10,5),(14,5),(9,4),   (11,5),(15,5),    (7,4),    (10,4),     (12,5),(16,5),(13,5),(17,5)**\n* **Step 2.13 | 13-Sum=20-7**\nSubset Removed: **[1,2,4]**\nSubset Explored:  **[1,2,10], [1,2,4,10]** \nBuffer Subset:  **[1,3,4],[10],    [4,10], [2,3,4],[1,10], [1,4,10], [1,2,3,4],[2,10], [2,4,10],[3,10], [3,4,10],[1,2,10], [1,2,4,10]**\nSubset Notes:    **(8,4),  (10,5),(14,5),(9,4),    (11,5),(15,5),    (10,4),     (12,5),  (16,5),   (13,5),(17,5),  (13,5),  (17,5)**\n* **Step 2.14 | 14-Sum=20-8**\nSubset Removed: **[1,3,4]**\nSubset Explored:  **[1,3,10], [1,3,4,10]** \nBuffer Subset:  **[10],     [4,10], [2,3,4],[1,10], [1,4,10], [1,2,3,4],[2,10], [2,4,10],[3,10], [3,4,10],[1,2,10], [1,2,4,10],[1,3,10], [1,3,4,10]**\nSubset Notes:    **(10,5),(14,5),(9,4),    (11,5),(15,5),    (10,4),     (12,5), (16,5),    (13,5),(17,5),(13,5), (17,5), (14,5), (18,5)**\n* **Step 2.15 | 15-Sum=20-9**\nSubset Removed: **[2,3,4]**\nSubset Explored:  **[2,3,10], [2,3,4,10]** \nBuffer Subset:  **[10], [4,10],    [1,10], [1,4,10], [1,2,3,4],[2,10], [2,4,10],[3,10], [3,4,10],[1,2,10], [1,2,4,10],[1,3,10], [1,3,4,10],[2,3,10], [2,3,4,10]**\nSubset Notes:    **(10,5),(14,5),(11,5),(15,5),(10,4),(12,5),(16,5),(13,5),(17,5),(13,5),(17,5),(14,5),(18,5),(15,5),(19,5)**\n* **Step 2.16 | 15-Sum=20-10**\nSubset Removed: **[1,2,3,4]**\nSubset Explored:  **[1,2,3,10], [1,2,3,4,10]** \nBuffer Subset:  **[10], [4,10], [1,10], [1,4,10],[2,10], [2,4,10],[3,10], [3,4,10],[1,2,10], [1,2,4,10],[1,3,10], [1,3,4,10],[2,3,10], [2,3,4,10],[1,2,3,10], [1,2,3,4,10]**\nSubset Notes:    **(10,5),(14,5),(11,5),(15,5),(12,5),(16,5),(13,5),(17,5),(13,5),(17,5),(14,5),(18,5),(15,5),(19,5),(16,5),(20,5)**\n\nWow. Solve it Manually. I Made It !! **In case my guide helps you. Please upvote to support.** \n\n**Performance:**\n```\nRuntime: 181 ms, faster than 100.00% of C++ online submissions for Find the K-Sum of an Array.\nMemory Usage: 59.4 MB, less than 66.67% of C++ online submissions for Find the K-Sum of an Array.\n```\n\n**C++ Code Example**\n```\nclass Solution {\npublic:\n    long long kSum(vector<int>& nums, int k) {\n        ios::sync_with_stdio(false);\n        cin.tie(nullptr);\n        long long sum=0, val, next, n=nums.size();\n        typedef pair<long long, long long> Data;\n        priority_queue<Data, vector<Data>, greater<Data>> buf;\n        for(long long i=0; i<n; ++i) {\n            if(nums[i]>=0) {\n                sum+=nums[i];\n            } else if(nums[i]<0){\n                nums[i]=-nums[i];\n            }\n        }\n        if(!--k)\n            return sum;\n        sort(nums.begin(), nums.end());\n        buf.push({nums[0], 1});\n        for(--k; k; --k) {\n            val=buf.top().first;\n            next=buf.top().second;\n            buf.pop();\n            if(next<n) {\n                buf.push({val+nums[next]-nums[next-1], next+1});\n                buf.push({val+nums[next], next+1});\n            }\n        }\n        return sum-buf.top().first;\n    }\n};\n```
['Greedy', 'Heap (Priority Queue)']