Hello coders!

Problem statement

Given an integer array, the values of the array need to separated into two subsets A and B whose intersection is null and whose unions the entire array. The sum of values in set A must be strictly greater than sum of values in set B, and number of elements in set A must be minimal. Return the values in set A.

Example explanation:

For eg. Given arr ={3,7,5,6,2}, here A would be {6,7}. Given arr = {2,3,4,4,5,9,7,8,6,10,4,5,10,10,8,4,6,4,10,1}, here A would be {8, 8, 9, 10, 10, 10, 10}.

Constraints:

1<=n<=10^5
1<=arr[i]<=10^5

UPD: Problem link. But the given solution is O(n*n) in the worst case and I want to solve it in less than O(n*n)