templates · Backtracking

Backtracking: combinations with pruning

  • "Pick k items" or "find all combinations that add up to target"
  • Order inside a group does not matter: [2, 3] and [3, 2] are the same answer
  • Can an item be reused? That one question decides i or i + 1 in the call

Backtracking: combinations & partitionsBacktracking with constraint pruning

the one rule

The invariant

The indexes picked into path never go down (each call loops only from start onwards), so each group is built in one order only.

write it from memory

The template

pick k from 1..n

javajava.util.*
/** Every way to pick k numbers from 1..n. */static List<List<Integer>> combine(int n, int k) {    List<List<Integer>> out = new ArrayList<>();    pick(1, n, k, new ArrayList<>(), out);    return out;} private static void pick(int start, int n, int k, List<Integer> path, List<List<Integer>> out) {    if (path.size() == k) {                           // picked enough: one answer        out.add(new ArrayList<>(path));        return;    }    int need = k - path.size();    for (int x = start; x <= n - need + 1; x++) {     // prune: leave room for the rest        path.add(x);                                  // choose        pick(x + 1, n, k, path, out);                 // next pick starts after x        path.remove(path.size() - 1);                 // un-choose    }}

The loop stops at n - need + 1: if fewer numbers remain than you still need, there is no point going on.

fill in the blanks — only these lines change per problem

  1. line 9When a group is finished: the right size, or the remaining target is 0.
  2. line 14The pruning bound: not enough items left, or the candidate is already too big.
  3. line 16Where the next choice starts: x + 1, so nothing is picked twice.

combination sum (reuse allowed)

javajava.util.*
/** Combination sum: distinct positive candidates, each may be used again; lists that add up to target. */static List<List<Integer>> combinationSum(int[] candidates, int target) {    int[] sorted = candidates.clone();    Arrays.sort(sorted);                              // sorted, so we can stop early    List<List<Integer>> out = new ArrayList<>();    reach(sorted, 0, target, new ArrayList<>(), out);    return out;} private static void reach(int[] c, int start, int remaining, List<Integer> path, List<List<Integer>> out) {    if (remaining == 0) {        out.add(new ArrayList<>(path));        return;    }    for (int i = start; i < c.length; i++) {        if (c[i] > remaining) break;                  // prune: every later one is bigger too        path.add(c[i]);        reach(c, i, remaining - c[i], path, out);     // i, not i + 1: reuse allowed        path.remove(path.size() - 1);    }}

Sort, then break as soon as a candidate is too big. Recurse with i because the same candidate may be used again.

fill in the blanks — only these lines change per problem

  1. line 18i here (reuse allowed). This one character is the whole difference from combination sum II.

combination sum II (each once, duplicates in input)

javajava.util.*
/** Combination sum II: candidates may repeat, each used at most once, no duplicate lists. */static List<List<Integer>> combinationSum2(int[] candidates, int target) {    int[] sorted = candidates.clone();    Arrays.sort(sorted);    List<List<Integer>> out = new ArrayList<>();    reachOnce(sorted, 0, target, new ArrayList<>(), out);    return out;} private static void reachOnce(int[] c, int start, int remaining, List<Integer> path, List<List<Integer>> out) {    if (remaining == 0) {        out.add(new ArrayList<>(path));        return;    }    for (int i = start; i < c.length; i++) {        if (i > start && c[i] == c[i - 1]) continue;  // same value at the same level: skip        if (c[i] > remaining) break;        path.add(c[i]);        reachOnce(c, i + 1, remaining - c[i], path, out); // i + 1: each used once        path.remove(path.size() - 1);    }}

Two changes from the reuse version: recurse with i + 1, and skip a value equal to the one before it at the same level.

fill in the blanks — only these lines change per problem

  1. line 16The duplicate rule for inputs with repeated values.

complexity

What it costs

time O(k · C(n, k)) for pick-k; exponential for target sums
There are C(n, k) groups of size k and each copy costs k. For target sums the count depends on the values; the break cuts every branch that is already too big.
space O(depth)
Only path and the recursion stack: at most k (or target ÷ smallest value) deep, apart from the answers.

watch out

Common bugs

  • Using break on an unsorted array. It is only safe because sorting makes every later candidate at least as big.
  • Recursing with start instead of i (or i + 1): you get the same group in many orders.
  • Making the call first and checking remaining < 0 inside it, instead of breaking before it. The answer is still right, but you explore many dead branches.

use it

Practise it on

learn it properly