369. Smallest Subset With Sum Greater Than All Other Elements

Given an array of n positive integers, find the smallest possible subset of elements whose sum is strictly greater than the sum of all the elements NOT picked. Print the picked elements, in non-increasing order, space-separated.

Input: The first line contains an integer n. The second line contains n space-separated positive integers. Output: Print the picked subset's elements in non-increasing order, space-separated.

1 <= n <= 10^5

The picked elements must be printed in NON-INCREASING order per the problem statement - since they were already selected in descending order during the greedy process, no additional sorting step is needed for the output.

Find the smallest group of numbers from an array whose sum exceeds the sum of everything NOT picked. Brute force: Try every possible subset size starting from 1, checking all combinations of that size for one whose sum exceeds the rest - this checks many subsets unnecessarily when a simple greedy ordering finds the answer directly. Optimised: Since picking the LARGEST available elements always contributes the most toward exceeding the remaining sum with the fewest picks, sorting descending and greedily adding elements one at a time (stopping the instant the condition is met) is provably optimal - no smaller subset (of any composition) could achieve the same condition with fewer picks.

Try every possible subset of the array (there are 2^n of them), compute the sum of the chosen elements and the sum of the rest, and check whether the chosen sum strictly exceeds the rest; among all subsets that satisfy this, keep the one with the fewest elements. This considers every possibility directly and is guaranteed correct, but the number of subsets to examine is exponential. Time: O(2^n * n) Space: O(n)

Sort the array in descending order with an efficient O(n log n) sort, compute the total sum once, then walk through the sorted array accumulating a running picked-sum and stopping as soon as it exceeds the sum of the remaining (unpicked) elements - which can be tracked incrementally as total minus picked-sum, avoiding any recomputation. This keeps the same greedy correctness argument as before but replaces the slow sort with an efficient one and computes the stopping condition in O(1) per step. Time: O(n log n) Space: O(n)

Sort the array in descending order using a simple quadratic sort (such as insertion sort or bubble sort), then repeatedly take the next-largest remaining element and add it to the picked set until the picked sum exceeds the sum of what remains. Greedily taking the largest elements first is provably optimal for minimizing the count needed (any smaller-count solution could be improved by swapping in a larger element), but using a quadratic sort to get the elements in order makes the whole approach slower than necessary. Time: O(n^2) Space: O(n)

1. Sort the array in DESCENDING order. 2. Greedily add the next-largest remaining element to the picked set. 3. Stop the moment the picked sum exceeds the sum of everything still remaining - taking the LARGEST elements first reaches this point with the fewest possible picks.

Time: O(n log n), dominated by the sort - the greedy accumulation pass afterward is O(n). Space: O(n) for the sorted array and the picked subset.

n = 1 (the single element is always the whole subset), n = 10^5 for performance, and arrays with many equal/duplicate values that affect the picking order.

Be ready to briefly justify why picking the LARGEST remaining elements (rather than any other order) minimizes the number of picks needed - each large element 'closes the gap' between picked and remaining sums fastest.