Subset Sums

The problem, simply

You get n numbers (they can be negative) and two limits A and B. Count the subsets whose sum is at least A and at most B. A subset is any choice of the numbers, including picking none (sum 0) and picking all.

This is the SPOJ problem SUBSUMS, where n can be up to 34. Trying all 2^34, about 17 billion, subsets is too slow. The trick gets it down to about 2^17, roughly 130 thousand, per half.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk the choice tree: for each number, take it or skip it. At the bottom, check whether the sum is in range.

class Solution {
    public long countSubsets(int[] v, long A, long B) {
        return walk(v, 0, 0, A, B);
    }

    private long walk(int[] v, int i, long sum, long A, long B) {
        if (i == v.length) return (sum >= A && sum <= B) ? 1 : 0;   // one finished choice
        return walk(v, i + 1, sum + v[i], A, B)    // take v[i]
             + walk(v, i + 1, sum, A, B);          // skip v[i]
    }
}

How long it takes: the tree has 2^n leaves, O(2^n). For n = 34 that is about 17 billion. Extra room: the tree is n levels deep, O(n).

Way 2: the clever way

Meet in the middle.

1. Split the numbers into a left half and a right half.
2. List every subset sum of the left half (2^(n/2) sums) and every subset sum of the right half. Sort the right sums.
3. For each left sum s, a right sum t works when A <= s + t <= B, that is A - s <= t <= B - s.
4. Count those t with two binary searches on the sorted right sums: the first position >= A - s and the first position > B - s. The gap between them is the count.
5. Add up the counts.

class Solution {
    public long countSubsets(int[] v, long A, long B) {
        int n = v.length, half = n / 2;
        long[] left = sums(v, 0, half);
        long[] right = sums(v, half, n);
        Arrays.sort(right);
        long count = 0;
        for (long s : left) {
            // right sums t with A - s <= t <= B - s
            count += firstAbove(right, B - s) - firstAtLeast(right, A - s);
        }
        return count;
    }

    // every subset sum of v[from..to-1], one per bitmask
    private long[] sums(int[] v, int from, int to) {
        int k = to - from;
        long[] out = new long[1 << k];
        for (int mask = 1; mask < (1 << k); mask++) {
            int low = Integer.numberOfTrailingZeros(mask);       // lowest chosen item
            out[mask] = out[mask & (mask - 1)] + v[from + low];  // reuse the smaller subset
        }
        return out;
    }

    private int firstAtLeast(long[] a, long key) {    // first index with a[i] >= key
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < key) lo = mid + 1; else hi = mid;
        }
        return lo;
    }

    private int firstAbove(long[] a, long key) {      // first index with a[i] > key
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] <= key) lo = mid + 1; else hi = mid;
        }
        return lo;
    }
}

How long it takes: building and sorting 2^(n/2) sums is O(2^(n/2) * n), and each of the 2^(n/2) left sums does two binary searches of O(n) steps. For n = 34 that is a few million steps. Extra room: the two lists of sums, O(2^(n/2)).

Watch out for

• The empty subset counts. Both halves include sum 0 (the empty choice), so the full empty set is counted once, when both halves pick nothing.
• Use long for sums and the count. The count alone can reach 2^34, which does not fit in int.
• 1 << k overflows for k >= 31. Each half here has at most 17 items, so it is fine.
• Sorting the left sums too lets you replace the binary searches with two pointers that only move one way. Same O(2^(n/2) * n) overall, a bit faster in practice.

What interviewers ask next

• Is there a subset with sum exactly S for n = 40? Same split, then look up S - s in a hash set of right sums.
• When the numbers are small and non-negative, use dynamic programming on the sum instead: dp[t] = number of ways to reach sum t. That is O(n * S), better when S is small.
• Closest subset sum to a target (LeetCode 1755). Meet in the middle, then for each left sum binary search the right sum nearest to target - s.
• Partition into two groups with the smallest difference, for n up to 30 per side (LeetCode 2035). Split by how many items each half gives to the first group, then match counts.

Remember this

Grown-up words: the take or skip tree is the subset recursion tree, splitting into halves is meet in the middle, the cards are subset sums, and "first at least" and "first above" are lower bound and upper bound.