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 $\leq min(1000, 2^n)$

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding on how to solve this problem.

Implement your solution in the following coding playground.