Subset Sum Problem

The problem, simply

You get a list of non negative whole numbers and a target sum. Can you choose some of the numbers (each one at most once) so that they add up to exactly sum? Answer yes or no.

Choosing nothing is allowed, so a target of 0 is always a yes.

A story to remember it

Picture it

Examples

Way 1: the simple way

Go through the numbers one by one. For each, ask two helpers: "can the rest make it if I take this one?" and "can the rest make it if I skip it?"

1. can(i, need): if need == 0, yes.
2. If there are no numbers left (i == n), no.
3. If nums[i] <= need and can(i + 1, need - nums[i]), yes.
4. Otherwise the answer is can(i + 1, need).

class Solution {
    public boolean isSubsetSum(int[] nums, int sum) {
        return can(nums, 0, sum);
    }

    private boolean can(int[] nums, int i, int need) {
        if (need == 0) return true;               // exact price paid
        if (i == nums.length) return false;       // no coins left
        if (nums[i] <= need && can(nums, i + 1, need - nums[i])) return true;  // take it
        return can(nums, i + 1, need);                                          // skip it
    }
}

How long it takes: two choices per number, O(2^n) in the worst case. Extra room: the call chain, O(n).

Way 2: the clever way

The helper only depends on (how many numbers looked at, sum needed). There are only (n + 1) x (sum + 1) such pairs. Fill them all in a table.

1. can[i][s]: can some of the first i numbers make exactly s?
2. Column 0 is all true. The rest of row 0 is false.
3. For number x in row i: can[i][s] = can[i-1][s] or (x <= s and can[i-1][s-x]).
4. The answer is can[n][sum].

class Solution {
    public boolean isSubsetSum(int[] nums, int sum) {
        int n = nums.length;
        boolean[][] can = new boolean[n + 1][sum + 1];
        for (int i = 0; i <= n; i++) can[i][0] = true;   // pick nothing

        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            for (int s = 1; s <= sum; s++) {
                can[i][s] = can[i - 1][s];                 // skip x
                if (x <= s && can[i - 1][s - x]) {
                    can[i][s] = true;                      // take x
                }
            }
        }
        return can[n][sum];
    }
}

How long it takes: one step per cell, O(n * sum). Extra room: the table, O(n * sum). This is fast only when sum is small. In computer science terms it is "pseudo polynomial": it grows with the value of sum, not with how many digits it has.

Watch out for

• A target of 0 is always true, even for an empty list.
• Negative numbers break the table, because indices like s - x can jump past sum. Shift all sums by the total of the negatives, or use a hash set of reachable sums.
• Big targets (in the billions) make the table too large. Then use meet in the middle: split the list in half, list all sums of each half (2^(n/2) each), sort one side and search for sum - a in it.

What interviewers ask next

• Do it with one row. can[s] |= can[s - x] for s from sum down to x. Room drops to O(sum).
• Print one valid subset. Keep the full table, then walk back from can[n][sum]: if can[i-1][s] is true, skip item i, else take it and move to s - x.
• Count the subsets that make sum. Replace "or" with "+": ways[i][s] = ways[i-1][s] + ways[i-1][s-x]. Watch out for zeros in the list, they double the count.
• Partition into two equal halves, or into two halves with the smallest difference. Both are this problem with target total / 2.
• Make it faster with bits: keep the reachable sums as a bitset and do bits |= bits << x.

Remember this

Grown-up words: the handful of coins is a subset, the yes or no chart is the subset sum DP table, take or skip is the 0/1 knapsack choice, and growing with the value of sum is pseudo polynomial time.