Smallest subset with sum greater than all other elements

The problem, simply

You get a list of positive numbers. Choose some of them so that their sum is strictly bigger than the sum of the numbers you did not choose.

Give back the smallest number of items you need to choose.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every group of bags. A group wins if its sum is more than total - sum. Keep the smallest winning group.

class Solution {
    public int minBags(int[] a) {
        int n = a.length;
        long total = 0;
        for (int x : a) total += x;
        int best = n;
        for (int mask = 1; mask < (1 << n); mask++) {
            long mine = 0;
            for (int i = 0; i < n; i++) if ((mask & (1 << i)) != 0) mine += a[i];
            if (mine > total - mine) best = Math.min(best, Integer.bitCount(mask));
        }
        return best;
    }
}

How long it takes: 2^n groups, each summed in n steps, O(2^n * n). Extra room: O(1).

Way 2: the clever way

For a fixed number of bags, the biggest bags give the biggest pile. So if any k bags can win, the k biggest bags win too. That means you only need to try the biggest bags in order.

1. Add up the total.
2. Sort the bags from biggest to smallest.
3. Take bags one by one, adding to mine. Stop as soon as mine > total - mine.

import java.util.Arrays;

class Solution {
    public int minBags(int[] a) {
        long total = 0;
        for (int x : a) total += x;
        Arrays.sort(a);                          // small to big, so we walk from the end
        long mine = 0;
        int bags = 0;
        for (int i = a.length - 1; i >= 0; i--) {
            mine += a[i];
            bags++;
            if (mine > total - mine) break;      // strictly more than the rest
        }
        return bags;
    }
}

How long it takes: the sort is O(n log n) and the walk is at most O(n). Extra room: O(1) beyond the sort.

Watch out for

• Use long for the sums. A hundred thousand numbers near a billion overflow int.
• Compare mine > total - mine, or 2 * mine > total. Do not compare with total / 2, because integer division rounds down and breaks on odd totals.
• Arrays.sort on an int[] sorts small to big. Walk from the end rather than boxing to Integer[] just to sort backwards.

What interviewers ask next

• Can you avoid a full sort? Build a max-heap in O(n) and pop the biggest bag until you are ahead. That is O(n + k log n) for k bags.
• If the numbers are small, like 1 to 100, count how many of each value there are and walk the counts from 100 down. That is O(n + 100).
• Return the chosen numbers in non-increasing order. LeetCode "Minimum Subsequence in Non-Increasing Order" is this exact problem.
• What if numbers can be negative? Sort and grab the biggest first, the same way. A negative number is never worth taking: it lowers your pile and raises the gap you must beat. If the total itself is negative, even taking nothing already wins, so check what the problem wants then.

Remember this

Grown-up words: the bags you grab are a subset, comparing with the rest is 2 * mine > total, grabbing the biggest first is a greedy choice, and "if any k bags win, the biggest k win" is the exchange argument that proves it.