Minimum Subsequence in Non-Increasing Order

Problem Description

Given the array nums, obtain a subsequence of the array whose sum of elements is strictly greater than the sum of the non-included elements in such subsequence. If there are multiple solutions, return the subsequence with minimum size and if there still exist multiple solutions, return the subsequence with the maximum total sum of all its elements. A subsequence of an array can be obtained by erasing some (possibly zero) elements from the array. Note that the solution with the given constraints is guaranteed to be unique. Also return the answer sorted in non-increasing order.

Key Insights

• The goal is to find a subsequence whose sum is greater than the sum of the remaining elements.
• Sorting the array in descending order helps to maximize the sum of the chosen subsequence while minimizing its size.
• A greedy approach works well here: keep adding elements from the sorted array until the condition is satisfied.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array. Space Complexity: O(n) - required for storing the result subsequence.

Solution

1. Sort the nums array in non-increasing order.
2. Calculate the total sum of the array.
3. Initialize a variable to keep track of the sum of the selected subsequence and an empty list for the result.
4. Iterate through the sorted array and keep adding elements to the subsequence until its sum is greater than the sum of the remaining elements.
5. Return the subsequence sorted in non-increasing order.

Code Solutions