[Python3] Finding next bigger sum from an all-positive sorted nums
Max k = 2000. The best strategy is finding next smaller sum one by one for 2000 times.\nHow to find next smaller sum?\nBiggest sum is the sum of all positive nu
Max k = 2000. The best strategy is finding next smaller sum one by one for 2000 times.\nHow to find next smaller sum?\nBiggest sum is the sum of all positive numbers. We start from there and finding the next smaller sum.\nTricky part:\nDon\'t "add" or "remove" numbers to or from subsequence. Instead, we introduce the concept of "use".\n"Use" a negative number means: **add** negative number to subsequence\n"Use" a positive number means: **remove** positive number from subsequence\nEither way "use" a number means reduce sum by abs(nums[i]) no matter positive or negative.\n"Un-use" a number does the reverse, it adds sum by abs(nums[i]) no matter positive or negative.\nA number in "use" cannot be used again. You must "un-use" it first.\nBy doing so, we can now make all numbers positive, and controlling the subsequence sum by choosing which number to "use" or "un-use".\n\nFirst we add all positive numbers to the sequence, making the biggest sum. In this subsequence, all numbers are in "not-in-use" state. Because for positive number, being picked means not in use, for negative number **not** being picked means not in use.\n\nWe make all numbers positive and sort them. Then one by one check which one to use or unuse from small to big.\nThe question becomes finding next bigger subsequence in this new all-positive sorted nums.\nThis can be achieved using heap.\n\n```\n    def kSum(self, nums: List[int], k: int) -> int:\n        maxSum = sum(v for v in nums if v>0)\n        if k==1: \n            return maxSum\n        absNums = sorted(abs(v) for v in nums)\n        que = [(absNums[0],0)]\n        for _ in range(k-1):\n            v,i = heapq.heappop(que) # subsequence with absNums[i] in use\n            if i+1<len(absNums):\n                heapq.heappush(que,(v-absNums[i]+absNums[i+1],i+1))\n                heapq.heappush(que,(v+absNums[i+1],i+1))\n        return maxSum-v\n```
[]