Code Implementation

class Solution:
    def minSubsequence(self, nums):
        nums.sort(reverse=True)
        total = sum(nums)
        curr_sum = 0
        res = []
        for num in nums:
            curr_sum += num
            res.append(num)
            if curr_sum > total - curr_sum:
                break
        return res
      

class Solution {
public:
    vector<int> minSubsequence(vector<int>& nums) {
        sort(nums.rbegin(), nums.rend());
        int total = accumulate(nums.begin(), nums.end(), 0);
        int curr_sum = 0;
        vector<int> res;
        for(int num : nums) {
            curr_sum += num;
            res.push_back(num);
            if(curr_sum > total - curr_sum) break;
        }
        return res;
    }
};
      

import java.util.*;
class Solution {
    public List<Integer> minSubsequence(int[] nums) {
        Arrays.sort(nums);
        int total = 0;
        for(int num : nums) total += num;
        int curr_sum = 0;
        List<Integer> res = new ArrayList<>();
        for(int i = nums.length - 1; i >= 0; i--) {
            curr_sum += nums[i];
            res.add(nums[i]);
            if(curr_sum > total - curr_sum) break;
        }
        return res;
    }
}
      

var minSubsequence = function(nums) {
    nums.sort((a, b) => b - a);
    let total = nums.reduce((a, b) => a + b, 0);
    let curr_sum = 0;
    let res = [];
    for(let num of nums) {
        curr_sum += num;
        res.push(num);
        if(curr_sum > total - curr_sum) break;
    }
    return res;
};
      

Problem Description

Given an array of integers nums, your task is to return the smallest possible subsequence (not necessarily contiguous) such that the sum of its elements is strictly greater than the sum of the remaining elements. The returned subsequence should be in non-increasing order (from largest to smallest).

• There is always at least one valid solution.
• You may not reuse elements; each element can only be picked once.
• If there are multiple answers, return the one with the largest elements first (i.e., sorted in non-increasing order).

Example:
Input: nums = [4,3,10,9,8]
Output: [10,9]

Thought Process

To solve this problem, we need a subsequence whose sum is more than half the total sum of the array. The most straightforward way is to try all possible subsequences, but this is very inefficient since the number of subsequences grows exponentially.

Instead, we should look for a way to quickly reach a sum greater than half. If we start by picking the largest numbers, we will reach a large sum faster and use fewer elements. This leads to the idea of sorting the array in descending order and picking numbers from the largest down until our picked sum exceeds the rest.

This is an example of a greedy algorithm: at each step, we make the most "greedy" choice (pick the largest number left) to move towards our goal.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Sort the array in non-increasing order (largest to smallest). This ensures that when we build our subsequence, we always pick the largest available number first, and that the result will be in the required order.
2. Compute the total sum of all elements in nums. This helps us know when our subsequence has a sum that's greater than the sum of the remaining elements.
3. Iterate through the sorted array, keeping a running sum of the elements we have picked so far.
4. After each pick, check if the sum of picked elements is greater than the sum of the rest (i.e., if picked_sum > total_sum - picked_sum). If it is, we can stop and return the picked elements as our answer.
5. Return the picked elements as the result. Since we picked from largest to smallest, the result will be in non-increasing order as required.

This approach is efficient because it only requires sorting and a single pass through the array.

Example Walkthrough

Let's use the sample input: nums = [4, 3, 10, 9, 8]

1. Sort in non-increasing order: [10, 9, 8, 4, 3]
2. Total sum = 10 + 9 + 8 + 4 + 3 = 34
3. Initialize picked_sum = 0, picked = []
4. Pick 10:
   picked_sum = 10
   remaining = 24
   10 > 24? No.
   picked = [10]
5. Pick 9:
   picked_sum = 19
   remaining = 15
   19 > 15? Yes.
   picked = [10, 9]
6. Since the condition is met, we stop and return [10, 9].

This matches the expected output.

Time and Space Complexity

Brute-force approach: Try all possible subsequences, sum them, and check the condition. Since there are 2ⁿ possible subsequences, this is O(2ⁿ) time and space, which is infeasible for large n.

Optimized (greedy) approach:

• Sorting: O(n log n)
• Single pass for picking elements: O(n)
• Total time: O(n log n) (sorting dominates)
• Space: O(n) for the sorted array and result subsequence

Summary

By sorting the array in non-increasing order and greedily picking the largest numbers until their sum exceeds the sum of the rest, we efficiently find the minimal subsequence required. This approach leverages a key insight: to reach a sum greater than half the total as quickly as possible, always start with the largest numbers. The result is both correct and optimal in terms of time and space, and the algorithm is simple and elegant.