Smallest Subset with Sum Greater than Rest

Smallest Subset with Sum Greater than the Rest is a clean greedy warm-up. It teaches the core greedy instinct: when you want a goal with the fewest pieces, grab the most powerful piece available at every step.

The slow way first

The brute-force idea: try every possible subset, check which ones have a sum greater than the rest, and keep the smallest. There are 2^n subsets, so this is exponential — hopeless for anything but tiny arrays.

The question to ask: if I am allowed only a fixed number of elements, how do I make their sum as large as possible? Obviously, pick the largest elements. So for a subset of any given size, the best possible sum uses the biggest numbers. That observation collapses the whole search.

The idea: grab the biggest, count as you go

Sort the array in descending order. Walk it from the front, adding each number to a running chosen sum. After each grab, compare chosen against the leftover rest = total - chosen. The moment chosen strictly exceeds rest, we are done — and because we always took the largest available numbers, no smaller subset could have reached that point.

The key insight: taking the largest remaining number each time grows chosen the fastest and shrinks rest the fastest, so we cross the line in the fewest possible steps.

Walk through it

Step through the animation. After sorting we have [9, 5, 4, 3, 1] with total 22. Take 9: chosen = 9, rest = 13 — not enough yet. Take 5: chosen = 14, rest = 8 — now 14 > 8, so we stop. The smallest subset is {9, 5}, just 2 elements.

Pseudocode

total = sum of all numbers
sort the numbers from largest to smallest
chosen = 0
for each number x in sorted order, counting from 1:
    chosen = chosen + x
    if chosen > total - chosen:      # chosen beats the leftover
        return the current count
return the count of all numbers      # (only if no strict majority is possible)

The Python solution

def min_subset(nums):
    total = sum(nums)
    nums.sort(reverse=True)
    chosen = 0
    for count, x in enumerate(nums, start=1):
        chosen += x
        if chosen > total - chosen:
            return count
    return len(nums)

• total is the sum of everything, computed once so we can derive rest cheaply.
• nums.sort(reverse=True) puts the largest numbers first — the heart of the greedy choice.
• enumerate(nums, start=1) gives both a running count and the value x, so count is already the subset size.
• chosen += x grows our running sum with the biggest available number.
• Line 7 is the test: chosen > total - chosen is the same as chosen beating the leftover rest. The first time it holds, count is the answer.

Complexity

The sort costs O(n log n) and the single pass is O(n), so the sort dominates. We use only a couple of accumulator variables, so extra space is O(1) (ignoring the sort).

When this pattern shows up

Practice