Find the K-Sum of an Array — LeetCode 2386 Python Solution

The problem

You are given an integer array nums and a positive integer k. You can choose any subsequence of the array and sum all of its elements together.

Example

Input

nums = [2,4,-2], k = 5

Output

2

Explanation

All the possible subsequence sums that we can obtain are the following sorted in decreasing order:

Python solution

class Solution:
    def kSum(self, nums: List[int], k: int) -> int:
        mx = 0
        for i, x in enumerate(nums):
            if x > 0:
                mx += x
            else:
                nums[i] = -x
        nums.sort()
        h = [(0, 0)]
        for _ in range(k - 1):
            s, i = heappop(h)
            if i < len(nums):
                heappush(h, (s + nums[i], i + 1))
                if i:
                    heappush(h, (s + nums[i] - nums[i - 1], i + 1))
        return mx - h[0][0]

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2386. Find the K-Sum of an Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems