TechPrep
Search spaces and optimisationReadLabPracticeCheck

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

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 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

Variants worth knowing

Test it like the interviewer will

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.

  1. Return all subsets of a list of distinct integers.
  2. Return all valid placements of n queens on an n x n board.
  3. 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.

Saved in this browser.