You are given a positive integer array nums and an integer k.

Your task is to choose at most k elements from nums such that their sum is maximized. There is one important restriction: all chosen numbers must be distinct (no duplicates allowed in your selection).

Return an array containing the chosen numbers in strictly descending order.

Key points to understand:

• Since all numbers in nums are positive, picking more elements always increases the sum. So to maximize the sum, you should pick as many elements as allowed — up to k of them.
• Because the chosen numbers must be distinct, if the array contains duplicates, each value can be used only once.
• To make the sum as large as possible, you should greedily pick the largest distinct values available.
• The final answer must be sorted in strictly descending order, which happens naturally when you pick the largest distinct values from biggest to smallest.

Example:

Suppose nums = [5, 3, 5, 8] and k = 3.

• The distinct values are {8, 5, 3}.
• Picking the largest 3 distinct values gives [8, 5, 3] with sum 16, which is the maximum possible.
• Note that we cannot pick 5 twice, even though it appears two times in the array.

If the number of distinct values in nums is less than k, you simply return all the distinct values in descending order.

The first observation is that every number in nums is positive. This means adding any element to our selection can only increase the total sum — it never hurts. So there is no reason to pick fewer elements than allowed: we should always try to pick exactly k elements (or all distinct values, if there are fewer than k of them).

The second observation comes from the distinctness constraint. Since each value can only be used once, duplicates in the array are useless beyond their first occurrence. We can mentally treat the array as a set of unique values.

Now the question becomes: given a set of distinct positive numbers, which k of them give the largest sum? The answer is clearly the k largest ones. This is a classic greedy choice — swapping any chosen number for a larger unchosen number would only increase the sum, so taking the biggest values first is always optimal.

How do we efficiently grab the largest distinct values? Sorting solves both problems at once:

• After sorting, the largest elements sit at the end of the array, so we can scan from right to left to pick big values first.
• Duplicates become adjacent after sorting, so detecting and skipping them is trivial: just compare each element with its neighbor nums[i] == nums[i + 1] and skip if they match.

Finally, since we collect elements while scanning from largest to smallest and skip duplicates, the result we build is automatically in strictly descending order — exactly the format the problem asks for. No extra sorting or post-processing is needed.

In short: positivity → take as many as possible; distinctness → skip duplicates; maximize sum → greedily take the largest; sorting → makes both the greedy pick and duplicate skipping easy.

Pattern Learn more about Greedy and Sorting patterns.

Following the reference approach, the solution uses sorting combined with a reverse traversal and a greedy selection pattern.

Step 1: Sort the array.

nums.sort()
n = len(nums)

Sorting nums in ascending order accomplishes two things at once:

• The largest values are placed at the end of the array.
• Any duplicate values become adjacent to each other, making them easy to detect.

Step 2: Traverse from the end (largest to smallest).

for i in range(n - 1, -1, -1):

We iterate from index n - 1 down to 0. This guarantees we always consider bigger values before smaller ones, which matches the greedy strategy of maximizing the sum.

Step 3: Skip duplicates.

if i + 1 < n and nums[i] == nums[i + 1]:
    continue

Since the array is sorted, a duplicate of nums[i] (if any) sits right next to it at index i + 1. If nums[i] equals nums[i + 1], the same value was already considered in a previous iteration, so we skip it. The check i + 1 < n simply guards against going out of bounds for the last element.

A subtle detail: this skipping rule effectively keeps only the occurrence at the smallest index of each duplicate group, but since all duplicates have the same value, which occurrence we keep does not matter.

Step 4: Greedily collect the element and count down k.

ans.append(nums[i])
k -= 1
if k == 0:
    break

Every distinct value we encounter is appended to ans. Because we traverse from largest to smallest and never append the same value twice, ans is built in strictly descending order automatically — no extra work needed. Once we have collected k elements, we stop early with break.

If the loop finishes before k reaches 0, it means the array has fewer than k distinct values, and ans correctly contains all of them.

Step 5: Return the result.

return ans

Complexity Analysis

• Time complexity: O(n log n), dominated by the sort. The reverse scan afterward is a single pass costing O(n).
• Space complexity: O(log n) for the sorting recursion stack (ignoring the output array ans).

Why this works

The correctness rests on three facts working together:

1. Greedy validity — with all-positive values, the k largest distinct values always yield the maximum sum.
2. Sorting as a tool — it orders values for the greedy pick and clusters duplicates for O(1) skip checks, avoiding the need for an extra hash set.
3. Free ordering — scanning from right to left produces the required strictly descending output as a natural by-product.

An alternative implementation could deduplicate first with a hash set, sort the unique values in descending order, and take the first k — same O(n log n) time, but the reference approach achieves it with a single sort and no auxiliary set.