Combinational Sum

The problem, simply

You get a list of different numbers, called candidates, and a target number. Find every group of candidates that adds up to the target. You may use the same number as many times as you like.

A group is about which numbers are in it, not their order. So 2 + 2 + 3 and 3 + 2 + 2 are the same group and must appear only once.

A story to remember it

Picture it

Examples

Way 1: the simple way

At every step, try every coin, in any order. When you hit exactly 0, sort the coins you used and drop the group in a set, so repeats vanish.

1. If nothing is left to pay, sort a copy of the picked coins and add it to a set.
2. If you paid too much, give up on this branch.
3. Otherwise, for each coin: put it down, try again with less to pay, then pick it back up.

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Set<List<Integer>> seen = new HashSet<>();
        tryAll(candidates, target, new ArrayList<>(), seen);
        return new ArrayList<>(seen);
    }

    private void tryAll(int[] cand, int left, List<Integer> picked, Set<List<Integer>> seen) {
        if (left == 0) {
            List<Integer> copy = new ArrayList<>(picked);
            Collections.sort(copy);            // 3,2,2 and 2,2,3 become the same list
            seen.add(copy);
            return;
        }
        if (left < 0) return;                  // paid too much
        for (int c : cand) {                   // any coin, in any order
            picked.add(c);
            tryAll(cand, left - c, picked, seen);
            picked.remove(picked.size() - 1);  // pick the coin back up
        }
    }
}

How long it takes: let t be the target and m the smallest coin. A path can be t/m coins deep, and each step tries all n coins, so there are up to n^(t/m) paths, and each answer is sorted. That is O(n^(t/m) * t/m). Extra room: the path and the call stack are at most t/m deep, O(t/m), not counting the answers.

Way 2: the clever way

Two small rules make the tree much smaller.

1. Sort the coins.
2. Remember a starting spot start. From a circle, only try coins at start or later. Pass the same i down (not i + 1), because a coin may be used again. This alone kills all repeats: groups are always built small to big.
3. If coin i is bigger than what is left, break. Every coin after it is even bigger.
4. When nothing is left, copy the picked list into the answer.

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);                  // small coins first
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] cand, int left, int start,
                           List<Integer> picked, List<List<Integer>> result) {
        if (left == 0) {
            result.add(new ArrayList<>(picked));  // paid exactly
            return;
        }
        for (int i = start; i < cand.length; i++) {
            if (cand[i] > left) break;            // this coin and all after it are too big
            picked.add(cand[i]);
            backtrack(cand, left - cand[i], i, picked, result);  // i, not i + 1: reuse allowed
            picked.remove(picked.size() - 1);     // undo the choice
        }
    }
}

How long it takes: in the worst case it is still about O(n^(t/m)) circles, because the number of answers itself can grow that fast. But no answer is built twice, no sorting or set is needed, and the break cuts whole fans of branches. Extra room: O(t/m) for the path and the call stack.

Watch out for

• Forgetting to sort. Without sorting, break is wrong because a later coin could still fit. Use continue if you cannot sort.
• Adding picked itself to the answer. It keeps changing. Add new ArrayList<>(picked).
• Starting the loop at 0 every time. That brings back the repeated groups from Way 1.
• A zero or negative coin makes the tree endless. The problem says all coins are positive; say so if asked.

What interviewers ask next

• Each number may be used once, and the input has repeats (Combination Sum II). Pass i + 1, and skip cand[i] == cand[i - 1] when i > start, so the same value is not tried twice at one level.
• Only count the ways, do not list them. That is the coin change counting problem: a 1D table ways[s] += ways[s - coin], looping coins on the outside, in O(n * t).
• What if order matters, so 2 + 3 and 3 + 2 are different? Loop the target on the outside and coins on the inside. That is Combination Sum IV.
• Pick exactly k numbers from 1 to 9 that add to n (Combination Sum III). Same tree, plus a depth limit of k.

Remember this

Grown-up words: the coins are candidates, the price is the target, the drawing is a recursion tree or state space tree, putting a coin down and picking it back up is backtracking, and the early break is pruning.