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.
We define the K-Sum of the array as the kth largest subsequence sum that can be obtained (not necessarily distinct).
Return the K-Sum of the array.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Note that the empty subsequence is considered to have a sum of 0.
Example 1:
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: - 6, 4, 4, 2, 2, 0, 0, -2. The 5-Sum of the array is 2.
Example 2:
Input: nums = [1,-2,3,4,-10,12], k = 16 Output: 10 Explanation: The 16-Sum of the array is 10.
Constraints:
n == nums.length1 <= n <= 105-109 <= nums[i] <= 1091 <= k <= min(2000, 2n)Problem Overview: You are given an integer array and a value k. A subsequence can include any subset of elements. Each subsequence produces a sum, and the task is to return the k-th largest subsequence sum. Because the number of subsequences is 2^n, generating all sums directly is infeasible for large n. Efficient solutions rely on ordering sums and exploring them incrementally.
Approach 1: Sorting and Binary Search (Time: O(n log n + n log S), Space: O(1) or O(n))
This approach begins by transforming the problem. Compute the maximum possible subsequence sum by adding all positive numbers. Then convert all elements to their absolute values and sort them. Instead of directly finding the k-th largest sum, you search for the k-th smallest reduction from the maximum sum. Binary search runs over the possible reduction values, while a DFS-style counting routine checks how many subsequences produce a reduction ≤ the candidate. The key insight: every subsequence sum equals maxSum - reduction. Binary search efficiently narrows the k-th reduction without enumerating all subsets. This approach is useful when you want deterministic exploration with predictable complexity.
Approach 2: Max-Heap and Iterative Summation (Time: O(n log n + k log n), Space: O(n))
This is the most common interview solution. First compute the maximum subsequence sum using all positive values. Convert numbers to absolute values and sort them. Instead of generating every subsequence sum, maintain candidates using a heap (priority queue). The heap tracks the next smallest reductions from the maximum sum. Start with the smallest reduction and iteratively expand possibilities by including the next absolute value or swapping elements in the reduction set. Each heap pop reveals the next largest subsequence sum. Because you only generate up to k candidates, the algorithm avoids exponential enumeration while maintaining correct order.
Recommended for interviews: The heap-based approach is usually what interviewers expect. It demonstrates control over priority queues, incremental state expansion, and ordering of candidate sums. The binary search method also works and shows strong reasoning about monotonic search spaces. Mentioning the naive 2^n subsequence enumeration first shows understanding of the brute-force baseline, but implementing the heap approach proves you can optimize it to O(n log n + k log n).
This approach involves generating all possible subsequence sums, sorting them, and then performing a binary search to find the k-th largest sum.
Given the constraints, this approach may not be feasible for the upper limits of n due to its time complexity. However, it illustrates a straightforward way to conceptualize the problem.
This solution generates all possible subsequences by using combinations from itertools, calculates their sums, and stores these in a list. The list is then sorted in descending order, and the k-th largest sum is returned by accessing the list at the k-1 index.
Python
JavaScript
Time Complexity: O(2^n * n) for generating subsequences and computing sums, and O(2^n log(2^n)) for sorting.
Space Complexity: O(2^n) for storing the sums.
This approach uses a max-heap (priority queue) to efficiently find the k-th largest subsequence sum. This method is more effective and feasible when handling large arrays.
The idea is to add sums to the heap and always maintain only the k largest sums, popping from the heap when necessary to ensure it does not grow beyond size k.
This Python solution maintains a max-heap of sums. We start with a heap initialized with 0, signifying the empty subsequence sum. For each number, we calculate potential new sums by adding the number to each current sum in the heap, expanding the list of sums. We then keep only the largest k elements in the heap. This ensures we eventually have the k-th largest sum at the k-1 index.
Time Complexity: O(n * k log k) due to maintaining a heap of size k across n iterations.
Space Complexity: O(k) for the heap storage.
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Binary Search | Time Complexity: O(2^n * n) for generating subsequences and computing sums, and O(2^n log(2^n)) for sorting. |
| Approach 2: Max-Heap and Iterative Summation | Time Complexity: O(n * k log k) due to maintaining a heap of size k across n iterations. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Binary Search | O(n log n + n log S) | O(1) - O(n) | When you can exploit monotonic search on reduction values and want deterministic search without maintaining many heap states |
| Max-Heap and Iterative Summation | O(n log n + k log n) | O(n) | Best general solution for interviews; efficiently generates the next largest subsequence sums using a priority queue |
Weekly Contest 307 | 2386. Find the K-Sum of an Array • codingMohan • 5,351 views views
Watch 4 more video solutions →Practice Find the K-Sum of an Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor