Minimum Subsequence in Non-Increasing Order

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.

LeetCode Problem - 1403

class Solution {
    public List<Integer> minSubsequence(int[] nums) {
        // Create a list to store the result subsequence
        List<Integer> answer = new ArrayList<>();

        // Calculate the total sum of the array
        int sum = 0;
        for(int e : nums){
            sum += e;
        }

        // Initialize variables: 
        // 'check' is used to track elements from the end of the sorted array
        // 'flag' is used to accumulate the sum of the chosen subsequence
        int check = 1;
        int flag = 0;

        // Sort the array in non-decreasing order so we can pick the largest elements first
        Arrays.sort(nums);

        // Loop until we find a subsequence where its sum is greater than the sum of the remaining elements
        while(true){
            // Pick the largest remaining element (from the end of the array)
            int temp = nums[nums.length - check];
            flag += temp;  // Add this element to the subsequence sum

            // If the sum of the subsequence is greater than the remaining elements' sum, break the loop
            if(flag > (sum - flag)){
                answer.add(temp);  // Add the element to the result list
                break;
            } else {
                // If the condition is not satisfied, continue adding the element to the list
                answer.add(temp);
            }
            check++;  // Move to the next largest element
        }
        // Return the final subsequence
        return answer;
    }
}