Description

Submission

class Solution {
public:
    vector<int> minSubsequence(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end(), greater<int>());
        vector<int> presum(n);
        presum[0] = nums[0];
        for(int i = 1; i < n; ++i) {
            presum[i] = presum[i-1] + nums[i];
        }
        
        auto iter = upper_bound(presum.begin(), presum.end(), presum.back() / 2);
        if(iter != presum.end()) {
            ++iter;
        }
        
        vector<int> rets;
        copy(nums.begin(), nums.begin() + (iter - presum.begin()), back_inserter(rets));
        return rets;
    }
};