Solution: Find the K-Sum of an Array

Explore an efficient method to determine the kth largest sum of subsequences within an integer array. Understand how to convert the problem using maximum positive sums, absolute values, and min heaps to reduce complexity. This lesson guides you through the algorithm and its time and space tradeoffs for solving the k-sum problem effectively.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

You are given an integer array, nums, and a positive integer k. Your task is to determine and return the $k^{th}$ largest possible sum among all subsequences of the array. A subsequence is formed by deleting no or more elements from the array without changing the order of the remaining elements. The sum of a subsequence is the total of its elements.

Remember: For valid subsequences:
The empty subsequence is valid, and its sum is considered $0$ .
Duplicate subsequence sums are allowed and counted separately when determining the $k^{th}$ largest.

Constraints:

$n ==$ nums.length
$1 \leq$ n $\leq 10^3$
$-10^3 \leq$ nums[i] ...