Problem Description

You are given an array nums of integers. Your task is to find a subsequence from this array such that the sum of elements in the subsequence is strictly greater than the sum of all the elements that are not included in the subsequence.

The subsequence you return must satisfy the following conditions:

1. It should have the minimum possible size (fewest elements)
2. If multiple subsequences have the same minimum size, choose the one with the maximum total sum
3. The answer must be returned sorted in non-increasing order (descending order)

A subsequence can be formed by removing some (possibly zero) elements from the original array while maintaining the relative order of remaining elements.

For example, if nums = [4,3,10,9,8], you would need to find the smallest subset of numbers whose sum is greater than the sum of the remaining numbers. The total sum is 34, so you need a subsequence with sum > 17. The answer would be [10,9] since 10+9=19 > 15 (which is 4+3+8).

The problem guarantees that the solution with the given constraints is unique.

Intuition

To find a subsequence whose sum is strictly greater than the sum of remaining elements, we need to think about what makes a subsequence optimal. Since we want the minimum size subsequence, we should be greedy and pick the largest elements first - this way we can reach the required sum threshold with fewer elements.

The key insight is that if the total sum of the array is S, then we need our subsequence sum to be greater than S/2. This is because if our subsequence has sum t, then the remaining elements have sum S - t. For our subsequence sum to be strictly greater than the remaining sum, we need t > S - t, which simplifies to t > S/2.

By sorting the array in descending order and greedily picking elements from largest to smallest, we achieve two goals:

1. We minimize the number of elements needed (since larger elements help us reach the threshold faster)
2. Among all minimum-size subsequences, we automatically get the one with maximum sum (since we're picking the largest available elements)

For example, if nums = [4,3,10,9,8] with total sum 34, we need our subsequence sum to exceed 17. After sorting in descending order [10,9,8,4,3], we pick:

• First 10: sum = 10 (not > 17)
• Then 9: sum = 19 (now 19 > 17, so we stop)

This greedy approach guarantees we find the optimal solution because once we exceed half the total sum with the largest possible elements, adding any more elements would only increase the size unnecessarily.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a greedy approach with sorting:

1. Calculate the total sum: First, we compute the sum of all elements in the array using sum(nums) and store it in variable s. This represents the total sum we need to split.

2. Sort in descending order: We sort the array in descending order using sorted(nums, reverse=True). This ensures we process elements from largest to smallest.

3. Greedy selection: We iterate through the sorted array and maintain:

   • ans: The result array that stores our subsequence
   • t: Running sum of elements in our subsequence

4. Check the stopping condition: For each element x in the sorted array:

   • Add x to the running sum: t += x
   • Append x to our answer array: ans.append(x)
   • Check if t > s - t (equivalently, if our subsequence sum is greater than the remaining sum)
   • If the condition is met, we break and return the answer

The algorithm works because:

• By taking elements in descending order, we minimize the number of elements needed
• The moment our subsequence sum exceeds half of the total sum (t > s - t is equivalent to t > s/2), we have found the minimum size subsequence
• Since we picked the largest elements first, this subsequence also has the maximum possible sum among all minimum-size subsequences
• The result is already in non-increasing order due to our sorting approach

Time Complexity: O(n log n) due to sorting, where n is the length of the input array.

Space Complexity: O(n) for storing the sorted array and the answer array.

Example Walkthrough

Let's walk through the solution with nums = [6, 7, 7, 9, 3, 2]:

Step 1: Calculate total sum

• Total sum s = 6 + 7 + 7 + 9 + 3 + 2 = 34
• We need our subsequence sum to be > 34/2 = 17

Step 2: Sort in descending order

• Sorted array: [9, 7, 7, 6, 3, 2]

Step 3: Greedy selection

• Initialize: ans = [], t = 0

Iteration 1:

• Pick element 9
• Update: t = 0 + 9 = 9, ans = [9]
• Check: Is 9 > 34 - 9? Is 9 > 25? No, continue

Iteration 2:

• Pick element 7
• Update: t = 9 + 7 = 16, ans = [9, 7]
• Check: Is 16 > 34 - 16? Is 16 > 18? No, continue

Iteration 3:

• Pick element 7
• Update: t = 16 + 7 = 23, ans = [9, 7, 7]
• Check: Is 23 > 34 - 23? Is 23 > 11? Yes, stop!

Step 4: Return result

• Return [9, 7, 7] (already in non-increasing order)

Verification:

• Subsequence sum: 9 + 7 + 7 = 23
• Remaining elements sum: 6 + 3 + 2 = 11
• Indeed, 23 > 11 ✓
• This is the minimum size (3 elements) needed to exceed half the total sum

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The dominant operation in this algorithm is the sorting of the array nums using sorted(nums, reverse=True), which takes O(n × log n) time where n is the length of the input array. The subsequent operations include:

• Computing the sum of all elements: O(n)
• Iterating through the sorted array once: O(n)

Since O(n × log n) dominates O(n), the overall time complexity is O(n × log n).

Space Complexity: O(log n)

The space complexity analysis considers:

• The ans list can grow up to O(n) in the worst case (when we need all elements)
• However, the dominant space consideration for complexity analysis is the auxiliary space used by the sorting algorithm
• Python's sorted() function uses Timsort, which requires O(log n) space for its recursive stack in the worst case
• The reference answer specifically states O(log n), which aligns with the auxiliary space used by the sorting operation

Therefore, the space complexity is O(log n), where n is the length of the array nums.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Sum Calculation

When dealing with large arrays or large integer values, calculating the total sum might cause integer overflow in some programming languages (though Python handles arbitrary precision integers automatically).

Pitfall Example:

# In languages with fixed integer sizes, this could overflow
total_sum = sum(nums)  # If nums contains very large values

Solution: In Python, this isn't an issue, but in other languages, use appropriate data types:

# For other languages, ensure using long/int64 types
# Or check for potential overflow before operations

2. Incorrect Stopping Condition

A common mistake is using the wrong comparison for determining when to stop adding elements to the subsequence.

Pitfall Example:

# Wrong: comparing with total_sum instead of remaining sum
if selected_sum > total_sum:  # This would require sum > total, which is impossible
    break

# Wrong: using >= instead of >
if selected_sum >= total_sum - selected_sum:  # "strictly greater" requirement
    break

Solution:

# Correct: ensure STRICTLY greater than remaining sum
if selected_sum > total_sum - selected_sum:
    break
# Or equivalently:
if selected_sum * 2 > total_sum:
    break

3. Forgetting to Sort or Sorting in Wrong Order

The greedy approach only works when we select elements from largest to smallest.

Pitfall Example:

# Wrong: sorting in ascending order
sorted_nums = sorted(nums)  # Would need more elements than necessary

# Wrong: not sorting at all
for num in nums:  # Original order might not give minimum size
    # ...

Solution:

# Correct: always sort in descending order
sorted_nums = sorted(nums, reverse=True)

4. Modifying Original Array

Some might try to sort the original array in-place, which could be problematic if the original array needs to be preserved.

Pitfall Example:

nums.sort(reverse=True)  # Modifies the original array
for num in nums:
    # ...

Solution:

# Create a new sorted array instead
sorted_nums = sorted(nums, reverse=True)
# Original nums array remains unchanged

5. Edge Case: Single Element Array

When the array has only one element, the subsequence must contain that element (sum of empty set is 0).

Pitfall Example:

# Might not handle nums = [1] correctly if logic is flawed
if len(nums) == 0:  # But what about len(nums) == 1?
    return []

Solution: The current implementation handles this correctly since:

• For nums = [1], total_sum = 1, selected_sum becomes 1
• Check: 1 > 0 (true), so returns [1]