Combination Sum (LeetCode 39)

You get an array of distinct positive integers, candidates, and a target. The goal is to find every combination of candidates that adds up to target. You can use the same number as many times as you want, and order doesn’t matter: [2, 2, 3] and [3, 2, 2] count as the same combination, so only one of them should show up.

For candidates = [2, 3, 6, 7] and target = 7, there are two combinations:

[2, 2, 3]
[7]

The idea

When I first worked through this, I wrote my plan as a comment right above the loop:

//approch:
    //1) scan through elements
    //2) consider adding an element (if eligible)
    //     2b) if element doesnt work, skip it
    //3) recurse
    //4) backtrack

That’s honestly the whole algorithm. I keep a running list, subArray, of the numbers I’ve picked so far, and instead of tracking the sum, I shrink target as I go. Each time I add a number, I recurse with target - candidates[i], the amount still left to make. When target hits exactly 0, subArray adds up to the original target, so I save a copy of it.

Then I take that number back off the list and try the next one. Same pattern as N-Queens: add, recurse, undo.

The code

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> subArray = new ArrayList<>();
        comboHelper(candidates, target, result, subArray, 0);
        return result;
    }

    public void comboHelper(int[] candidates, int target, List<List<Integer>> result, List<Integer> subArray, int index) {
        if (target == 0) {
            result.add(new ArrayList<>(subArray));
            return;
        }
        // start at index, not 0, so each combination is only built in one order
        for (int i = index; i < candidates.length; i++) {
            if (candidates[i] > target) {
                continue;  // too big, skip it
            }
            subArray.add(candidates[i]);
            comboHelper(candidates, target - candidates[i], result, subArray, i);  // i, not i + 1: we can reuse candidates[i]
            subArray.remove(subArray.size() - 1);  // backtrack
        }
    }
}

Can `target` go negative?

My first version had this check sitting at the top of comboHelper, commented out:

//if (target < 0) {
    //We've overstepped. is this possible? need to test
//    return; //exit!
//}

Turns out it isn’t possible, and the reason is step 2b of my plan. Before I add a number, I check whether it’s bigger than what’s left of target, and if it is, I skip it. So I only ever subtract a number that fits, and target can get down to 0 but never past it. The check would never fire, so it’s gone.

The other way to write this is to add every number, let target go negative, and have that check bail out at the top of the next call. That works too, but it makes a recursive call just to find out it went too far. Checking before I add skips that call entirely.

The `index` parameter

This is the part that keeps the answers from repeating. My original comment for it was:

// index variable gets udpated as we go through the algorithm as per the spec

Each call only looks at candidates from index onward, never the ones before it. And when I recurse, I pass i, not i + 1. Those two details do two different jobs:

Passing i lets me pick the same number again. After adding a 2, the next call can still pick another 2, which is how [2, 2, 3] gets built.
Starting at index means that once I’ve moved past a number, I never go back to it. So every combination gets built in one order only, with the numbers in the same order they appear in candidates.

To see why the second one matters, here’s what happens if the loop starts at 0 instead of index, on the same example:

[2, 2, 3]
[2, 3, 2]
[3, 2, 2]
[7]

Same combination, three times, just in different orders. Starting at index cuts that down to just [2, 2, 3].

Runtime

Let $N$ be the number of candidates, $T$ the target, and $M$ the smallest candidate. Every number I add is at least $M$ , so a combination can have at most $T/M$ numbers, which means the recursion goes at most $T/M$ calls deep. Each call loops over at most $N$ candidates, so the search tree has at most about $N^{T/M}$ leaves. That gives a loose upper bound of $O(N^{T/M + 1})$ , and the “too big, skip it” check cuts off a lot of those branches in practice.

For space, the recursion and subArray both go at most $T/M$ deep, so that’s $O(T/M)$ , not counting the combinations I return.

combination-sum.html