O(n * klogk) solution + clever tricks
Starting point: given a multiset of subsequence sums sl, adding an element x in nums results in a new multiset of subsequence sums sl.extend([n + x for n in sl]
Starting point: given a multiset of subsequence sums `sl`, adding an element `x` in `nums` results in a new multiset of subsequence sums `sl.extend([n + x for n in sl])`. We want to keep the top `k` of them. However, straight implementation of this is too slow.\n\nIntuition: if `x` is negative, we probably don\'t have to change `sl` much. More precisely, if `len(sl) == k` already, we only have to consider the new sums from the current max down to the smallest possible sum `sl[index]` such that `sl[index] + x` is at least as big as the current k-sum. If `len(sl) < k`, adjust the index downward by at most `k - len(sl)` accordingly. We can do this inplace with a bit of index traversal trick. This trick helps more than it sounds because the `abs(x)` is bounded (`-10 ** 9 <= x <= 10 ** 9`), so the top `k` subsequence sums quickly grow to such magnitude relative to `x` that few changes will be made.\n\nWhat about `x >= 0`? All top `k` subsequence sums shift upward by `x`, and then interleave with the original sums that are big enough. So, we keep track of the accumulative upward shifts. Then after the shift, it looks as if `x` is subtracted from the original sums: `x = -x`. The solution is then finally fast enough.\n\n...I can\'t believe all these tricks are required to solve this \uD83D\uDE26\n```\nfrom sortedcontainers import SortedList\n\nclass Solution:\n    def kSum(self, nums: List[int], k: int) -> int:\n        sl = SortedList([0])\n        base = 0\n        for x in nums:\n            if x >= 0:\n                base += x\n                x = -x\n            index = sl.bisect_left(sl[0] - x)\n            if len(sl) < k:\n                index -= k - len(sl)\n                index = max(0, index)\n            while index < len(sl):\n                sl.add(sl[index] + x)\n                index += 2\n                if len(sl) > k:\n                    sl.pop(0)\n                    index -= 1\n        return sl[0] + base\n```
['Python']