Simple solution with a detailed proof | Heap | NlogN + klogK
I got very frustrated when I failed to tackle this problem and people are sharing their code w/o any proof like "I just know it". Inspired by ye15, finally I co
I got very frustrated when I failed to tackle this problem and people are sharing their code w/o any proof like "I just know it". Inspired by [ye15](https://leetcode.com/problems/find-the-k-sum-of-an-array/discuss/2456675/Python3-priority-queue), finally I come up with a proof for this problem.\n\n## The idea\n\nObviously, the largest sum (`posSum`) is the sum of all positive numbers. Using `posSum` as a baseline, we now substract numbers from it. Note that "adding a negative number" and "removing a positive number" are the same in effect, all we care about is a subset of absolute values of `nums`.  For k-th largest sum, we need get the k-th smallest (in terms of sum of items) of such subsets.\n\nFor k-th largest, we\'ll need to consider all combinations. The problem is *how to do this while controlling the size of candidates*.\n\n- Use heap to track all candidates, so we can extract the minimum in `log` time.\n- Enumerate the combinations in a treeish way, so we only need to check the root before go into deeper leafs.\n\nOnce we get the k-th smallest subset, we know the k-th largest sum is `posSum - sum(<k-th smallest subset>)`.\n\n## The proof\nThe most important problem is **how to define this tree**. It\'s defined as:\n\n- Let `nums` be the absolute values of `nums`, and sorted increasingly.\n- The value of root node is the smallest `num`\n- On level `i+1`, each node has two children.\n\t- The value of left child is its `parent + nums[i+1]`\n\t- The value of right child is its `parent + nums[i+1] - nums[i]`\n\nNote that all subsets on level `i` contain the element `nums[i]`, that meas nodes on level `i` are the subsets which ends with `nums[i]`.\n\nAnd this tree has two important features:\n\n1. **Each path starting from root defines a subset**: when we go left, we keep `nums[i]`; when we go right, we remove `nums[i]`.\n2. **Both left/right child >= parent**:\n\t- Left: `parent + nums[i+1] >= parent`\n\t- Right: `parent + nums[i+1] - nums[i] >= parent`, that\'s because we already sorted nums, so `nums[i+1] >= nums[i]`.\n\nFrom (1) we know this tree covers all possible `2**n` subsets, the tree is a variant of [decision tree](https://en.wikipedia.org/wiki/Decision_tree), in which path from node to internal node is also a valid decision path.\nFrom (2) we know children is always larger than parent, so we need use parent first. This indicates that only after parent is used and removed, then we need add children as candidates.\n\n## The code\n\n```javascript\nvar kSum = function(nums, k) {\n    let posSum = nums.reduce((prev, curr) => curr > 0 ? prev + curr : prev, 0)\n    nums = nums.map(x => Math.abs(x)).sort((l, r) => l - r)\n    let heap = new Heap([{sum: nums[0], i: 0}], (l, r) => l.sum - r.sum)\n    let ans = posSum\n    for (let i = 1; i < k; i++) {\n        let {sum, i} = heap.pop()\n        ans = posSum - sum\n        if (i + 1 >= nums.length) continue\n        heap.push({sum: sum + nums[i + 1], i: i + 1})\n        heap.push({sum: sum - nums[i] + nums[i + 1], i: i + 1})\n    }\n    return ans\n};\n```\n\nNote that the `Heap` class is from [harttle/contest.js](https://github.com/harttle/contest.js/blob/master/src/heap.mjs), here\'s my submission: https://leetcode.com/submissions/detail/779204351/\n
['Heap (Priority Queue)', 'JavaScript']