An expedition team is packing supply crates before setting off into the wilderness. Each crate has a known weight. Rather than splitting supplies evenly, the quartermaster wants to build a single "reserve" bundle containing the fewest possible crates such that the total weight carried in the reserve is strictly greater than the total weight of every crate left behind at base camp. Among all ways of choosing the fewest crates that satisfy this rule, the quartermaster always ends up with the heaviest crates available (there is exactly one multiset of weights that achieves the minimum count). Report the weights placed in the reserve, listed from heaviest to lightest.
Print the weights of the crates placed in the reserve, space-separated, in non-increasing order.
Example 1
Input
5 4 3 10 9 8
Expected
10 9
Explanation
Total weight is 34. Taking only the heaviest crate (10) leaves 24 behind, not enough (10 is not > 24). Taking the two heaviest (10 and 9) sums to 19, which is strictly greater than the 15 left behind (3+4+8=15), so 2 is the minimum reserve size. The reserve is {10, 9}, printed heaviest first.
Example 2
Input
4 1 1 1 1
Expected
1 1 1
Explanation
All crates weigh 1, total 4. Two crates sum to 2, which only ties the remaining 2 (not strictly greater), so 2 crates are not enough. Three crates sum to 3, strictly greater than the remaining 1, so the minimum reserve size is 3, all weighing 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →