[Python3] Heap/Priority Queue, O(NlogN + klogk)
Initial Observation\n1. Given n can be as large as 10^5, the time complexity of this problem has to be no worse than log-linear.\n2. This problem is dealing wit
**Initial Observation**\n1. Given `n` can be as large as `10^5`, the time complexity of this problem has to be no worse than log-linear.\n2. This problem is dealing with *subsequences* but not *subarrays*, indicating we can shuffle the order of the original array, e.g. by sorting it.\n3. Given `-10^9 <= nums[i] <= 10^9`, indicating we need to be *clever* when dealing with positive and negative numbers.\n4. Given we need to return the `k`-th largest subsequence sum, indicating we can use a min-heap to store the possible results.\n\n**Implementation**\n1. We find the sum of all positive numbers. This is the maximum possible sum among all subsequence sums. We initialize our min-heap `ans` to be `[maxSum]`.\n2. We create an array `absNums` of the absolute values, sorted from smallest to largest.\n3. We create a max-heap `maxHeap`. It will start with one pair in it. That pair will be `(maxSum - absNums[0], 0)`. The pairs are compared each time with largest sum first.\n4. Before we have `k` elements in `ans`, we will:\n```\npop (nextSum, i) from maxHeap\npush nextSum to ans\nif i + 1 < N:\n\tpush (nextSum + absNums[i] - absNums[i + 1], i + 1) to maxHeap\n\tpush (nextSum - absNums[i + 1], i + 1) to maxHeap\n```\n\n**Why we need two pushs following each pop from the max-heap?** (by @gonpachiro)\nIn this [post](https://stackoverflow.com/a/33220735), [David Eisenstat](https://stackoverflow.com/users/2144669/david-eisenstat) shared an intuitive explanation. Basically, we maintain a tree-structure via a min-heap to record the subsequence sums. Each time we delete a node, we insert its children. This way, we don\'t need to calculate every subsequence sum explicitly (i.e. by adding and subtracting rather than summing from scratch).\n\n**Complexity**\nTime Complexity: `O(NlogN + klogk)` for sorting and heap operations\nSpace Complexity: `O(N + k)`, for using `absNums`, `ans` and `maxHeap`\n \n **Solution**\n```\nclass Solution:\n    def kSum(self, nums: List[int], k: int) -> int:\n        maxSum = sum([max(0, num) for num in nums])\n        absNums = sorted([abs(num) for num in nums])\n        maxHeap = [(-maxSum + absNums[0], 0)]\n        ans = [maxSum]\n        while len(ans) < k:\n            nextSum, i = heapq.heappop(maxHeap)\n            heapq.heappush(ans, -nextSum)\n            if i + 1 < len(absNums):\n                heapq.heappush(maxHeap, (nextSum - absNums[i] + absNums[i + 1], i + 1))\n                heapq.heappush(maxHeap, (nextSum + absNums[i + 1], i + 1))\n        return ans[0]\n```\n\nPlease upvote if you find the solution helpful. Kudos to [btilly](https://stackoverflow.com/users/585411/btilly)\'s [post](https://stackoverflow.com/questions/72114300) for inspiration.\n\n**Cleaner Solution Using One Heap** (by @celestez)\n```\nclass Solution:\n    def kSum(self, nums: List[int], k: int) -> int:\n        maxSum = sum([max(0, num) for num in nums])\n        absNums = sorted([abs(num) for num in nums])\n        maxHeap, nextSum = [(-maxSum + absNums[0], 0)], -maxSum\n        for _ in range(k - 1):\n            nextSum, i = heapq.heappop(maxHeap)\n            if i + 1 < len(absNums):\n                heapq.heappush(maxHeap, (nextSum - absNums[i] + absNums[i + 1], i + 1))\n                heapq.heappush(maxHeap, (nextSum + absNums[i + 1], i + 1))\n        return -nextSum\n```
['Heap (Priority Queue)', 'Python', 'Python3']