<p>You are given an integer array <code>nums</code> and a <strong>positive</strong> integer <code>k</code>. You can choose any <strong>subsequence</strong> of the array and sum all of its elements together.</p>

<p>We define the <strong>K-Sum</strong> of the array as the <code>k<sup>th</sup></code> <strong>largest</strong> subsequence sum that can be obtained (<strong>not</strong> necessarily distinct).</p>

<p>Return <em>the K-Sum of the array</em>.</p>

<p>A <strong>subsequence</strong> is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.</p>

<p><strong>Note</strong> that the empty subsequence is considered to have a sum of <code>0</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,4,-2], k = 5
<strong>Output:</strong> 2
<strong>Explanation:</strong> All the possible subsequence sums that we can obtain are the following sorted in decreasing order:
- 6, 4, 4, 2, <u>2</u>, 0, 0, -2.
The 5-Sum of the array is 2.
</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= k &lt;= min(2000, 2<sup>n</sup>)</code></li>
</ul>

'''
Input:
    nums (List[int]): [2, 4, -2]
    k (int): 5
Output:
    2, find the 5-sum of the array

Constraint:
    len(nums) > 0 -> True
    k >= 1 -> True
    k <= 2^n -> True

Approach: Sorting + Min-Heap
    1. answer: Sum(positive number) - Sum(k-th smallest subsequence):
    2. How do we find (k+1)th smallest subseq. using (k)th smallest subseq.:
        1. Option 1: Remove a small positive number from the subseq
        2. Option 2: Add a negative number into the subseq.
        3. If we convert everything into positive, then we can only focus on option 1:
        4. Using sorting, we can easily find the smallest positive number avaialble
        ex: Given [2, 4, -2]:
            1. Sum(positive): 2 + 4 = 6
            2. Convert everything into positive:
                [2, 4, 2]
            3. Sort the array:
                [2, 2, 4]
            4. Use min-heap to iteratively find the curr_smallest_subseq
    3. How to iteratively find the curr_smallest_subseq:
       1. Sum(1-th smallest subsequence):
            0
        2. Sum(2-th smallest subseq):
            it would be: arr[0] 
        3. Sum(k-th smallest subseq) using Sum(k-1 th smallest subseq):
            1. We put (arr[0], 0) into the min-heap:
            2. We repeat the process by k - 1 times:
                1. Pop out (curr_smallest_sum, idx) from the min-heap:
                    This means that arr[idx] is the largest element in the subseq.
                2. To obtain the next smallest sum, there are two possibilities:
                    1. Remove arr[idx], adding arr[idx + 1]:
                        Add (curr_smallest_sum - arr[idx] + arr[idx + 1], idx + 1) into the heap
                    2. Add arr[idx]
                        Add (curr_smallest_sum + arr[idx + 1], idx + 1) into the heap
            3. After step 2:
                curr_smallest_sum would be Sum(k-th smallest subseq.)
    4. Finally we return Sum(positive number) - curr_smallest_sum`

TC: O(nlgn + klgk), n denotes the size of the `nums`
    Sorting - O(nlgn)
    Using min-heap for O(k) operations takes O(k lgk)

SC: O(k)
    min-heap at most stores O(k * 2) = O(k) elements

'''
import heapq
class Solution:
    def kSum(self, nums: List[int], k: int) -> int:
        sum_positive = sum([num for num in nums if num > 0])

        # Convert everything into positive
        nums = [abs(num) for num in nums]

        # Sort the array
        nums.sort()

        # Find the k-th smallest subseq sum
        min_h = [(nums[0], 0)]
        curr_smallest_sum = 0
        for i in range(k - 1):
            curr_smallest_sum, idx = heapq.heappop(min_h)

            if idx + 1 < len(nums):
                heapq.heappush(min_h, (curr_smallest_sum + nums[idx + 1] - nums[idx], idx + 1))
                heapq.heappush(min_h, (curr_smallest_sum + nums[idx + 1], idx + 1))
        
        return sum_positive - curr_smallest_sum
        
535