Backtracking: Generate Combinations, Permutations, and Paths

Think in choices and state

For a backtracking problem, identify (1) the state that describes the partial answer, (2) the choices available next, and (3) the condition that means the answer is complete. Recursively explore each legal choice. When the recursive call returns, undo the mutation so the next branch starts from the original state.

This pattern appears in subsets, permutations, combinations that sum to a target, Sudoku, and path enumeration. Its worst-case time is often exponential because the number of valid candidates itself may be exponential. Pruning helps skip branches that cannot lead to a result, but does not necessarily change the worst-case bound.

Example: combinations that sum to a target

Given positive candidate values that may be reused, choose numbers in nondecreasing index order. This avoids generating the same combination in a different order.

def combination_sum(candidates, target):
    answers = []
    path = []
    candidates.sort()

    def search(start, remaining):
        if remaining == 0:
            answers.append(path.copy())
            return
        for i in range(start, len(candidates)):
            value = candidates[i]
            if value > remaining:
                break
            path.append(value)
            search(i, remaining - value)
            path.pop()

    search(0, target)
    return answers

Passing i allows the current value to be selected again; passing i + 1 instead would restrict each candidate to one use. Copy the path when saving a result, because the working list is later mutated during backtracking.

Pruning and correctness

Sorting enables the early break: once a candidate exceeds the remaining positive target, every later candidate is too large as well. Other useful pruning rules include stopping when a partial sum already exceeds a target, rejecting a board that violates a constraint, or checking whether enough elements remain to complete a selection.

• State exactly what a recursive call represents.
• Make progress toward a base case in every recursive branch.
• Undo every mutation after the recursive call, even when a branch fails.
• Decide whether duplicates are meaningful and skip equivalent choices deliberately.