We want to find the kth sum of subsequences from an array. We can do this by first taking the sum of all the positive numbers in the array (m) and then starting off with that as our first sum of a subsequence. Then, we want to make smaller subsequence sums, which can be done by either adding negative numbers or dropping positive numbers (hence why vals is an abs(num)). We also want to remove previous visits as well.
class Solution:
def kSum(self, nums: List[int], k: int) -> int:
m = sum(num for num in nums if num > 0)
pq = [(-m, 0)]
vals = sorted(abs(num) for num in nums)
for _ in range(k):
num, i = heappop(pq)
if 0 < i < len(vals):
heappush(pq, (num+vals[i], i+1))
heappush(pq, (num-vals[i-1]+vals[i], i+1))
continue
if i < len(vals):
heappush(pq, (num+vals[i], i+1))
return -num