Solution: Find the K-Sum of an Array

Let’s solve the Find the K-Sum of an Array problem using the Top K Element Pattern.

Statement

You are given an integer array, nums, and a positive integer k. Your task is to determine and return the kthk^{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 00.

  • Duplicate subsequence sums are allowed and counted separately when determining the kthk^{th} largest.

Constraints:

  • n==n == nums.length

  • 11 \leq n 103\leq 10^3

  • 103-10^3 \leq nums[i] 103\leq 10^3

  • 1<=1 <= k

Solution

A brute-force approach to this problem will involve generating all possible subsequences of the array. Since an array of length n has exactly 2n2^{n} subsequences, this method becomes infeasible for large n (up to 1000).

To solve the problem efficiently, we reframe the task: instead of directly computing the kthk^{th}largest subsequence sum from all 2n2^{n} possibilities, we observe that the maximum possible subsequence sum is the sum of all positive numbers in the array. Every other valid subsequence sum can be interpreted as subtracting some “loss” from this maximum.

Thus, finding the kthk^{th}largest subsequence sum is equivalent to finding the (k1)th(k−1)^{th} smallest loss (i.e., reduction) and subtracting it from the total sum of positive numbers.

To compute these losses, we transform the problem as follows:

  • Convert all elements to absolute values—as excluding positives or including negatives both reduce the total.

  • Sort this array to prioritize smaller losses.

  • Use a min heap to systematically explore the smallest reduction combinations.

We initialize the heap with (loss = 00, index = 00) and generate candidates by:

  • Including the current value: (currLoss + nums[i], i+1)

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.