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

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

Constraints:

• $n ==$ nums.length

• $1 \leq$ n $\leq 10^3$

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

• $1 <=$ k

A brute-force approach to this problem will involve generating all possible subsequences of the array. Since an array of length n has exactly $2^{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 $k^{th}$ ...