Backtracking
Build candidates one choice at a time, undo each choice on the way back, and prune branches that cannot succeed.
Combination Sum. Given distinct positive candidates and a target, return every unique combination that sums to target. A number may be used any number of times. Return combinations in ascending order.
Signals that point here
- "Return all" subsets, permutations, combinations, partitions, placements.
- Constraint puzzles: N-queens, sudoku, word search on a grid.
- Small
n(up to ~20), because the output itself can be exponential.
The idea
The template is always choose, explore, un-choose. A start index stops the search from producing the same combination in a different order; recursing with i rather than i + 1 is what allows reuse.
Sorting first enables pruning: once a candidate exceeds the remaining sum, every later one does too, so break instead of continue. Pruning is where interviewers look for judgement.
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
candidates = sorted(candidates)
result: list[list[int]] = []
path: list[int] = []
def explore(start: int, remain: int) -> None:
if remain == 0:
result.append(path[:]) # copy: path keeps changing
return
for i in range(start, len(candidates)):
if candidates[i] > remain:
break # sorted, so the rest are too big
path.append(candidates[i]) # choose
explore(i, remain - candidates[i])
path.pop() # un-choose
explore(0, target)
return resultpublic static class Backtracking
{
public static List<List<int>> CombinationSum(int[] candidates, int target)
{
var sorted = candidates.OrderBy(x => x).ToArray();
var result = new List<List<int>>();
var path = new List<int>();
void Explore(int start, int remain)
{
if (remain == 0) { result.Add(new List<int>(path)); return; } // copy
for (int i = start; i < sorted.Length; i++)
{
if (sorted[i] > remain) break; // sorted, so the rest are too big
path.Add(sorted[i]); // choose
Explore(i, remain - sorted[i]);
path.RemoveAt(path.Count - 1); // un-choose
}
}
Explore(0, target);
return result;
}
}Complexity
Exponential in the worst case: roughly O(k ยท N^(T/m)) for N candidates, target T, smallest candidate m, and k the output length. Say it is bounded by the output size and that pruning cuts it in practice.
Pitfalls interviewers watch for
- Appending
pathitself instead of a copy, so every result ends up empty. - Starting the loop at 0 each time, which produces
[2,3]and[3,2]. continueinstead ofbreakafter sorting: correct but loses the pruning.
Variants worth knowing
- Subsets: record
pathat every node, recurse withi + 1. - Permutations: a
usedarray instead of astartindex. - Candidates with duplicates (Combination Sum II): sort, recurse with
i + 1, skipcandidates[i] == candidates[i - 1]wheni > start.
Test it like the interviewer will
combination_sum([2, 3, 6, 7], 7)returns[[2, 2, 3], [7]]combination_sum([2, 3, 5], 8)returns[[2, 2, 2, 2], [2, 3, 3], [3, 5]]combination_sum([2], 1)returns[]combination_sum([7, 3, 2], 7)returns[[2, 2, 3], [7]]- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: combination_sum([3, 2, 5], 8)
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- Return all subsets of a list of distinct integers.
- Return all valid placements of
nqueens on ann x nboard. - Determine whether a word exists in a grid of letters, moving between adjacent cells without reuse.
Check yourself
What are the three steps of the backtracking template?
Choose, explore, un-choose.
What does the start index prevent?
Producing the same combination in a different order.