Subset Sum Problem

The problem, simply

You get a list of non-negative numbers and a target. Can you choose some of the numbers, each at most once, so that they add up to exactly the target? Answer true or false.

Choosing no numbers at all is allowed, and it adds up to 0.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each number, branch twice: take it, or skip it. Carry how much is still needed.

1. If nothing is still needed, answer true.
2. If the numbers ran out, or the need went below 0, this branch fails.
3. Otherwise try taking the number (need goes down by it), and if that fails, try skipping it.

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

    private boolean pick(int[] nums, int i, int need) {
        if (need == 0) return true;                       // exact match
        if (i == nums.length || need < 0) return false;   // out of numbers, or too much
        return pick(nums, i + 1, need - nums[i])          // take nums[i]
            || pick(nums, i + 1, need);                   // skip nums[i]
    }
}

How long it takes: two branches per number, O(2^n). Extra room: the call stack is n deep, O(n).

The tree asks the same small question many times: "using numbers from i on, can I make need?" There are only n * (target + 1) different such questions. That is the hint for Way 2.

Way 2: the clever way

Build a yes or no table. can[i][s] answers: using only the first i numbers, can I make the sum s?

1. Row 0 uses no numbers, so only s = 0 is yes.
2. For row i with the number x:
   • Skip x: if can[i - 1][s] was yes, it is still yes.
   • Take x: if s >= x and can[i - 1][s - x] was yes, then s is yes too.
3. The answer is can[n][target].

class Solution {
    public boolean isSubsetSum(int[] nums, int target) {
        int n = nums.length;
        boolean[][] can = new boolean[n + 1][target + 1];
        can[0][0] = true;                                  // no numbers make only 0
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            for (int s = 0; s <= target; s++) {
                can[i][s] = can[i - 1][s]                  // skip x
                    || (s >= x && can[i - 1][s - x]);      // take x
            }
        }
        return can[n][target];
    }

    // the same idea with one row, walking s from big to small
    public boolean isSubsetSumOneRow(int[] nums, int target) {
        boolean[] can = new boolean[target + 1];
        can[0] = true;
        for (int x : nums) {
            for (int s = target; s >= x; s--) {
                if (can[s - x]) can[s] = true;             // big to small: x is used once
            }
        }
        return can[target];
    }
}

How long it takes: one box for every number and every sum, O(n * target). Extra room: the full table is O(n * target), and the one row version needs only O(target).

This is fast when the target is small. If the target is a billion, the table is too big, and the problem is NP-complete in general.

Watch out for

• Forgetting can[0][0] = true. Then nothing can ever become true.
• Negative numbers. The table index s - x breaks, and the "need below 0" stop in Way 1 is wrong. Shift the sums by the total of the negatives, or ask if negatives are allowed.
• In Way 1, checking need < 0 before need == 0 is fine, but checking i == nums.length before need == 0 misses a match made with the last number.

What interviewers ask next

• Print one subset. Fill the 2D table, then walk back from can[n][target]: if the box above is yes, skip that number; otherwise take it and move left by its value.
• List every subset. Use Way 1 with a list that you add to and remove from, and save a copy whenever the need hits 0.
• Count the subsets. Store counts instead of yes or no: ways[s] += ways[s - x], walking s from big to small.
• Split into two equal halves (Partition Equal Subset Sum). Run this with target = total / 2, after checking the total is even.
• Make the difference of two groups as small as possible. Fill the table up to total / 2 and take the biggest reachable sum s. The answer is total - 2s.

Remember this

Grown-up words: the take or skip tree is backtracking over subsets, the repeated small questions are overlapping subproblems, the yes table is a 2D dynamic programming table, and the one row trick is the 0/1 knapsack space saving.