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.

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.

Examples

Example 1

1
2
3
4
5

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

1
2
3

Input: nums = [1,-2,3,4,-10,12], k = 16
Output: 10
Explanation: The 16-Sum of the array is 10.

Constraints

  • n == nums.length
  • 1 <= n <= 10^5
  • -109 <= nums[i] <= 10^9
  • 1 <= k <= min(2000, 2n)

Solution

Method 1 – Max-Heap and Subset Sums

Intuition

The largest possible subsequence sum is the sum of all positive numbers. To find the k-th largest, we can sort the absolute values, use a max-heap to generate possible sums by removing elements, and always expand the next largest sum by removing the next smallest absolute value. This is similar to finding the k-th largest sum in a sorted array of subset sums.

Approach

  1. Sort nums by absolute value in descending order.
  2. Compute the sum of all positive numbers as the maximum sum.
  3. Use a max-heap to keep track of possible sums and their indices.
  4. For each step, pop the largest sum, and push new sums by removing the next element (if not already removed).
  5. Repeat this process k times to get the k-th largest sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    long long kSum(vector<int>& nums, int k) {
        long long total = 0;
        for (int &x : nums) if (x > 0) total += x;
        vector<long long> arr;
        for (int x : nums) arr.push_back(abs(x));
        sort(arr.begin(), arr.end());
        priority_queue<pair<long long, int>> pq;
        set<pair<long long, int>> seen;
        pq.push({total, 0});
        seen.insert({0, 0});
        long long ans = total;
        while (--k) {
            auto [sum, i] = pq.top(); pq.pop();
            if (i < arr.size()) {
                pq.push({sum - arr[i], i + 1});
                if (i > 0) pq.push({sum - arr[i] + arr[i-1], i + 1});
            }
            ans = sum;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

func kSum(nums []int, k int) int64 {
    total := int64(0)
    for _, x := range nums {
        if x > 0 {
            total += int64(x)
        }
    }
    arr := make([]int, len(nums))
    for i, x := range nums {
        if x < 0 {
            arr[i] = -x
        } else {
            arr[i] = x
        }
    }
    sort.Ints(arr)
    type node struct{ sum, idx int64 }
    h := &maxHeap{}
    heap.Init(h)
    heap.Push(h, node{total, 0})
    var ans int64
    for k > 0 {
        cur := heap.Pop(h).(node)
        ans = cur.sum
        k--
        if cur.idx < int64(len(arr)) {
            heap.Push(h, node{cur.sum - int64(arr[cur.idx]), cur.idx + 1})
            if cur.idx > 0 {
                heap.Push(h, node{cur.sum - int64(arr[cur.idx]) + int64(arr[cur.idx-1]), cur.idx + 1})
            }
        }
    }
    return ans
}
// maxHeap implementation omitted for brevity
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public long kSum(int[] nums, int k) {
        long total = 0;
        for (int x : nums) if (x > 0) total += x;
        int[] arr = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) arr[i] = Math.abs(nums[i]);
        Arrays.sort(arr);
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));
        pq.offer(new long[]{total, 0});
        long ans = total;
        while (k-- > 0) {
            long[] cur = pq.poll();
            ans = cur[0];
            int i = (int)cur[1];
            if (i < arr.length) {
                pq.offer(new long[]{cur[0] - arr[i], i + 1});
                if (i > 0) pq.offer(new long[]{cur[0] - arr[i] + arr[i-1], i + 1});
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun kSum(nums: IntArray, k: Int): Long {
        var total = 0L
        for (x in nums) if (x > 0) total += x
        val arr = nums.map { Math.abs(it) }.sorted()
        val pq = PriorityQueue<Pair<Long, Int>>(compareByDescending { it.first })
        pq.add(Pair(total, 0))
        var ans = total
        var kk = k
        while (kk-- > 0) {
            val (sum, i) = pq.poll()
            ans = sum
            if (i < arr.size) {
                pq.add(Pair(sum - arr[i], i + 1))
                if (i > 0) pq.add(Pair(sum - arr[i] + arr[i-1], i + 1))
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import heapq
class Solution:
    def kSum(self, nums: list[int], k: int) -> int:
        total = sum(x for x in nums if x > 0)
        arr = sorted(abs(x) for x in nums)
        h = [(-total, 0)]
        seen = set()
        seen.add((0, 0))
        ans = total
        for _ in range(k):
            s, i = heapq.heappop(h)
            ans = -s
            if i < len(arr):
                heapq.heappush(h, (s + arr[i], i + 1))
                if i > 0:
                    heapq.heappush(h, (s + arr[i] - arr[i-1], i + 1))
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn k_sum(nums: Vec<i32>, k: i32) -> i64 {
        let total: i64 = nums.iter().filter(|&&x| x > 0).map(|&x| x as i64).sum();
        let mut arr: Vec<i64> = nums.iter().map(|&x| (x as i64).abs()).collect();
        arr.sort();
        let mut heap = std::collections::BinaryHeap::new();
        heap.push((total, 0));
        let mut ans = total;
        for _ in 0..k {
            let (sum, i) = heap.pop().unwrap();
            ans = sum;
            if i < arr.len() {
                heap.push((sum - arr[i], i + 1));
                if i > 0 {
                    heap.push((sum - arr[i] + arr[i-1], i + 1));
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    kSum(nums: number[], k: number): number {
        let total = 0;
        for (const x of nums) if (x > 0) total += x;
        const arr = nums.map(x => Math.abs(x)).sort((a, b) => a - b);
        const pq: [number, number][] = [[-total, 0]];
        let ans = total;
        for (let t = 0; t < k; ++t) {
            const [s, i] = pq.shift()!;
            ans = -s;
            if (i < arr.length) {
                pq.push([s + arr[i], i + 1]);
                if (i > 0) pq.push([s + arr[i] - arr[i-1], i + 1]);
                pq.sort((a, b) => a[0] - b[0]);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n + k log n), where n is the length of nums, for sorting and heap operations.
  • 🧺 Space complexity: O(n + k), for the heap and arrays used.