Smallest subset with sum greater than all other elements

Problem Statement

Given an array of positive integers, find the minimum number of elements such that their sum is strictly greater than the sum of the remaining elements.

Constraints:

• 1 ≤ n ≤ 10^5
• 1 ≤ arr[i] ≤ 10^9

Example:

• Input: arr = [3, 1, 7, 1]
• Output: 1
• Explanation: Total sum = 12. Selecting [7] gives sum = 7 > remaining sum = 5.

Example 2:

• Input: arr = [2, 1, 2]
• Output: 2
• Explanation: Total sum = 5. Need [2, 2] with sum = 4 > remaining sum = 1. Selecting one 2 gives 2 which is not > 3.

Approach 1: Brute Force (All Subsets)

Intuition

Generate all possible subsets, calculate their sum, and find the smallest subset whose sum is greater than the sum of remaining elements.

Algorithm

1. Generate all subsets of the array
2. For each subset, calculate sum
3. Check if subset sum > (total sum - subset sum)
4. Track minimum subset size satisfying the condition

import java.util.*;

public class Solution {
    private int minSubset = Integer.MAX_VALUE;
    
    private void generateSubsets(int[] arr, int idx, int currentSum, 
                                 int count, int totalSum) {
        if (currentSum > totalSum - currentSum) {
            minSubset = Math.min(minSubset, count);
            return;
        }
        
        if (idx == arr.length) return;
        
        // Include current element
        generateSubsets(arr, idx + 1, currentSum + arr[idx], count + 1, totalSum);
        
        // Exclude current element
        generateSubsets(arr, idx + 1, currentSum, count, totalSum);
    }
    
    public int smallestSubset(int[] arr) {
        int totalSum = 0;
        for (int num : arr) totalSum += num;
        
        minSubset = Integer.MAX_VALUE;
        generateSubsets(arr, 0, 0, 0, totalSum);
        
        return minSubset;
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - Generating all subsets
• Space Complexity: O(n) - Recursion stack depth

Approach 2: Greedy with Sorting (Optimal)

Intuition

To minimize the number of elements, we should greedily pick the largest elements first. Sorting in descending order and picking elements until our sum exceeds half the total gives the optimal solution.

Why Greedy Works:

• We need subset sum > remaining sum
• This means subset sum > total_sum / 2
• Picking largest elements first reaches this threshold with minimum count

Algorithm

1. Calculate total sum of array
2. Sort array in descending order
3. Keep adding elements until sum > total_sum - sum
4. Return count of elements added

import java.util.*;

public class Solution {
    public int smallestSubset(int[] arr) {
        long totalSum = 0;
        for (int num : arr) totalSum += num;
        
        // Sort in descending order
        Integer[] boxedArr = Arrays.stream(arr).boxed().toArray(Integer[]::new);
        Arrays.sort(boxedArr, Collections.reverseOrder());
        
        long subsetSum = 0;
        int count = 0;
        
        for (int num : boxedArr) {
            subsetSum += num;
            count++;
            
            // Check if subset sum > remaining sum
            if (subsetSum > totalSum - subsetSum) {
                break;
            }
        }
        
        return count;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] arr = {3, 1, 7, 1};
        System.out.println(sol.smallestSubset(arr));  // Output: 1
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n log n) - Dominated by sorting
• Space Complexity: O(1) - In-place sorting, constant extra space

Alternative: Using Half Sum Threshold

Key Takeaways

1. Greedy Strategy: Always pick the largest remaining element
2. Mathematical Insight: Need sum > total/2 for subset to be greater
3. Sorting is Key: Sorting enables greedy selection of largest elements
4. Early Termination: Stop as soon as condition is satisfied
5. Edge Case: When all elements are equal, need more than half the elements
6. Optimization: Use partial_sort if only top few elements needed (O(n + k log n))
7. Strictly Greater: Remember the condition is >, not >=