Problem

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.

Examples

Example 1:

1
2
3
4
5

Input:
nums = [4,3,10,9,8]
Output:
 [10,9] 
Explanation: The subsequences [10,9] and [10,8] are minimal such that the sum of their elements is strictly greater than the sum of elements not included. However, the subsequence [10,9] has the maximum total sum of its elements. 

Example 2:

1
2
3
4
5

Input:
nums = [4,4,7,6,7]
Output:
 [7,7,6] 
Explanation: The subsequence [7,7] has the sum of its elements equal to 14 which is not strictly greater than the sum of elements not included (14 = 4 + 4 + 6). Therefore, the subsequence [7,6,7] is the minimal satisfying the conditions. Note the subsequence has to be returned in non-decreasing order.

Solution

Method 1 – Greedy with Max Heap

Intuition

The key idea is to always pick the largest available numbers first to quickly surpass half the total sum. By using a max heap, we efficiently extract the largest elements until the selected subsequence sum is strictly greater than the sum of the remaining elements. This ensures the subsequence is minimal in size and has the maximum possible sum.

Approach

  1. Compute the total sum of the array.
  2. Insert all elements into a max heap (priority queue).
  3. Repeatedly extract the largest element, add it to the answer, and update the running sum.
  4. Stop when the running sum becomes strictly greater than the sum of the remaining elements.
  5. Return the answer list in the order of extraction (which is already non-increasing).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
	vector<int> minSubsequence(vector<int>& nums) {
		priority_queue<int> pq(nums.begin(), nums.end());
		int total = accumulate(nums.begin(), nums.end(), 0);
		int sub = 0;
		vector<int> ans;
		while (sub <= total - sub) {
			int x = pq.top(); pq.pop();
			ans.push_back(x);
			sub += x;
		}
		return ans;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func minSubsequence(nums []int) []int {
	h := &IntHeap{}
	total := 0
	for _, n := range nums {
		heap.Push(h, -n)
		total += n
	}
	ans := []int{}
	sub := 0
	for sub <= total-sub {
		x := -heap.Pop(h).(int)
		ans = append(ans, x)
		sub += x
	}
	return ans
}

type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
	public List<Integer> minSubsequence(int[] nums) {
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		int total = 0, sub = 0;
		for (int n : nums) {
			pq.offer(n);
			total += n;
		}
		List<Integer> ans = new ArrayList<>();
		while (sub <= total - sub) {
			int x = pq.poll();
			ans.add(x);
			sub += x;
		}
		return ans;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
	fun minSubsequence(nums: IntArray): List<Int> {
		val pq = PriorityQueue<Int>(compareByDescending { it })
		var total = 0
		nums.forEach {
			pq.add(it)
			total += it
		}
		val ans = mutableListOf<Int>()
		var sub = 0
		while (sub <= total - sub) {
			val x = pq.poll()
			ans.add(x)
			sub += x
		}
		return ans
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
	def minSubsequence(self, nums: list[int]) -> list[int]:
		import heapq
		total: int = sum(nums)
		nums = [-n for n in nums]
		heapq.heapify(nums)
		ans: list[int] = []
		sub: int = 0
		while sub <= total - sub:
			x = -heapq.heappop(nums)
			ans.append(x)
			sub += x
		return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
	pub fn min_subsequence(nums: Vec<i32>) -> Vec<i32> {
		use std::collections::BinaryHeap;
		let mut pq = BinaryHeap::from(nums.clone());
		let total: i32 = nums.iter().sum();
		let mut sub = 0;
		let mut ans = Vec::new();
		while sub <= total - sub {
			let x = pq.pop().unwrap();
			ans.push(x);
			sub += x;
		}
		ans
	}
}

Complexity

  • Time: O(n log n) (heap operations for n elements)
  • Space: O(n) (heap and answer storage)