# Find the K-Sum of an Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-k-sum-of-an-array)
Canonical: https://scaleengineer.com/dsa/problems/find-the-k-sum-of-an-array
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Hubspot](https://scaleengineer.com/companies/hubspot)
---
## 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`.

**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.length`
* `1 <= n <= 105`
* `-109 <= nums[i] <= 109`
* `1 <= k <= min(2000, 2n)`

# Approaches
## Brute Force: Generate All Subsequence Sums
A naive but fundamental approach is to generate all possible `2^n` subsequences of the input array. For each subsequence, we calculate the sum of its elements. These sums are then collected, sorted in descending order, and the `k`-th element is selected as the result. This method is exhaustive and guarantees the correct answer but is computationally expensive.
**Time:** `O(n * 2^n)` for generating and summing all subsequences, plus `O(2^n * log(2^n))` for sorting. The total is `O(n * 2^n)`. · **Space:** `O(2^n)` to store all the subsequence sums.
**Pros:** Conceptually simple and easy to implement.; Guaranteed to be correct.
**Cons:** Extremely high time and space complexity.; Infeasible for the given constraints where `n` can be up to 10^5.
### Explanation
The core of this method is the generation of all subsequences. This can be achieved using recursion (backtracking) or iteratively using bit manipulation. In the bit manipulation approach, each integer from `0` to `2^n - 1` represents a unique subsequence. The `j`-th bit of an integer `i` corresponds to the `j`-th element of `nums`. If the `j`-th bit is set, the `j`-th element is included in the subsequence corresponding to `i`. After computing all `2^n` sums, a standard sorting algorithm is used to order them, from which the `k`-th largest is easily retrieved.

```java
public long kSum(int[] nums, int k) {
    int n = nums.length;
    List<Long> sums = new ArrayList<>();
    // Iterate through all possible subsequences using bitmask
    for (int i = 0; i < (1 << n); i++) {
        long currentSum = 0;
        for (int j = 0; j < n; j++) {
            if ((i & (1 << j)) != 0) {
                currentSum += nums[j];
            }
        }
        sums.add(currentSum);
    }
    Collections.sort(sums, Collections.reverseOrder());
    return sums.get(k - 1);
}
```
### Algorithm
*   Create a list, `sums`, to store the subsequence sums.
*   Iterate from `i = 0` to `2^n - 1`. Each `i` represents a bitmask for a subsequence.
*   For each `i`, initialize `currentSum = 0`.
*   Iterate from `j = 0` to `n - 1`.
*   If the `j`-th bit is set in `i`, add `nums[j]` to `currentSum`.
*   After the inner loop, add `currentSum` to the `sums` list.
*   Sort the `sums` list in descending order.
*   Return the element at index `k - 1` in the sorted list.

## Problem Transformation with a Min-Heap
A highly efficient approach hinges on a clever transformation of the problem. Instead of dealing with positive and negative numbers, we can reframe the problem as finding the k-th smallest "deviation" from a maximum possible sum. This simplifies the search space and allows us to use a min-heap to efficiently find the desired value, leveraging the small constraint on `k`.
**Time:** `O(n log n + k log k)`. Sorting the absolute values takes `O(n log n)`. The heap operations involve `k-1` extractions and about `2*(k-1)` insertions, with heap size up to `O(k)`, leading to `O(k log k)`. Total time is `O(n log n)`. · **Space:** `O(n)`. `O(n)` to store the absolute values (if not done in-place) and `O(k)` for the priority queue.
**Pros:** Highly efficient, with time complexity dominated by sorting.; Effectively utilizes the small `k` constraint.; Reduces a complex problem to a standard heap-based search.
**Cons:** The core insight of problem transformation is not immediately obvious.; The logic for generating new candidates for the heap requires careful reasoning.
### Explanation
First, we observe that the largest possible subsequence sum is achieved by taking all positive numbers. Let's call this `maxSum`. Any other subsequence sum `S` can be seen as `maxSum` minus some value. This "deviation" comes from two sources: not including a positive number `p` (which is like subtracting `p` from `maxSum`) or including a negative number `n` (which is like subtracting `abs(n)` from `maxSum`). Therefore, any subsequence sum `S` can be written as `S = maxSum - deviation`, where `deviation` is a sum of a subsequence of `abs(nums)`. Finding the k-th largest `S` is equivalent to finding the k-th smallest `deviation`.
The problem is now reduced to: find the k-th smallest subsequence sum of an array of non-negative numbers (`abs(nums)`). We can solve this efficiently using a min-heap. We sort `abs(nums)` and use the heap to generate the smallest subsequence sums in order. The smallest deviation is 0 (from an empty subsequence). We initialize the heap with the next smallest deviation (`abs(nums)[0]`) and iteratively generate larger deviations by either adding the next element or replacing the last added element. We repeat this `k-1` times to find the k-th smallest deviation.

```java
import java.util.*;

class Solution {
    public long kSum(int[] nums, int k) {
        int n = nums.length;
        long maxSum = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                maxSum += nums[i];
            }
            nums[i] = Math.abs(nums[i]);
        }

        Arrays.sort(nums); // nums now contains absolute values, sorted

        // Min-heap to store {deviation_sum, index}
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        
        long currentDeviation = 0;
        if (n > 0) {
            pq.offer(new long[]{nums[0], 0});
        }

        // We already have the 1st largest sum (maxSum), which corresponds to deviation 0.
        // We find the k-th smallest deviation by popping from the heap k-1 times.
        for (int i = 1; i < k; i++) {
            long[] top = pq.poll();
            currentDeviation = top[0];
            int index = (int) top[1];

            if (index + 1 < n) {
                // Option 1: Add the next element to the current subsequence
                pq.offer(new long[]{currentDeviation + nums[index + 1], index + 1});
                
                // Option 2: Replace the last element of the current subsequence with the next one
                pq.offer(new long[]{currentDeviation - nums[index] + nums[index + 1], index + 1});
            }
        }

        return maxSum - currentDeviation;
    }
}
```
### Algorithm
*   Initialize `maxSum = 0`. Iterate through `nums`, adding all positive numbers to `maxSum`.
*   Convert every number in `nums` to its absolute value.
*   Sort the modified `nums` array (which now contains absolute values) in ascending order.
*   If `k` is 1, the answer is `maxSum` (corresponding to a deviation of 0).
*   Initialize a min-priority queue `pq` to store pairs of `{deviation_sum, index}`.
*   Push the smallest non-zero deviation, `{nums[0], 0}`, into `pq`.
*   Initialize `currentDeviation = 0`.
*   Loop `k-1` times (from `i=1` to `k-1`):
    *   Pop the top element `{sum, idx}` from `pq`. This is the next smallest deviation. Set `currentDeviation = sum`.
    *   If `idx + 1` is within the array bounds:
        *   Generate a new candidate by adding the next element: `sum + nums[idx + 1]`. Push `{sum + nums[idx + 1], idx + 1}` to `pq`.
        *   Generate another candidate by replacing the current element with the next: `(sum - nums[idx]) + nums[idx + 1]`. Push `{(sum - nums[idx]) + nums[idx + 1], idx + 1}` to `pq`.
*   The final answer is `maxSum - currentDeviation`.

# Solutions
### Java

```java
class Solution { public long kSum ( int [] nums , int k ) { long mx = 0 ; int n = nums . length ; for ( int i = 0 ; i < n ; ++ i ) { if ( nums [ i ] > 0 ) { mx += nums [ i ]; } else { nums [ i ] *= - 1 ; } } Arrays . sort ( nums ); PriorityQueue < Pair < Long , Integer >> pq = new PriorityQueue <>( Comparator . comparing ( Pair: : getKey )); pq . offer ( new Pair <>( 0L , 0 )); while (-- k > 0 ) { var p = pq . poll (); long s = p . getKey (); int i = p . getValue (); if ( i < n ) { pq . offer ( new Pair <>( s + nums [ i ], i + 1 )); if ( i > 0 ) { pq . offer ( new Pair <>( s + nums [ i ] - nums [ i - 1 ], i + 1 )); } } } return mx - pq . peek (). getKey (); } }
```

### CPP

```cpp
using pli = pair < long long , int > ; class Solution { public: long long kSum ( vector < int >& nums , int k ) { long long mx = 0 ; int n = nums . size (); for ( int i = 0 ; i < n ; ++ i ) { if ( nums [ i ] > 0 ) { mx += nums [ i ]; } else { nums [ i ] *= - 1 ; } } sort ( nums . begin (), nums . end ()); priority_queue < pli , vector < pli > , greater < pli >> pq ; pq . push ({ 0 , 0 }); while ( -- k ) { auto p = pq . top (); pq . pop (); long long s = p . first ; int i = p . second ; if ( i < n ) { pq . push ({ s + nums [ i ], i + 1 }); if ( i ) { pq . push ({ s + nums [ i ] - nums [ i - 1 ], i + 1 }); } } } return mx - pq . top (). first ; } };
```

### Python

```python
class Solution : def kSum ( self , nums : List [ int ], k : int ) -> int : mx = 0 for i , v in enumerate ( nums ): if v > 0 : mx += v else : nums [ i ] = - v 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 ]
```