Backtracking, pruning and branch-and-bound | DSA

← BlogDATA STRUCTURES / ALGORITHMSPython example pack ↓

Backtracking constructs a partial solution, chooses a candidate, explores, then undoes the choice. Choose→explore→unchoose isolates neighbouring branches. N-queens tracks columns and diagonals; Sudoku can choose the cell with fewest candidates.

Pruning is safe only when no valid or better solution remains. Branch-and-bound uses objective bounds against the incumbent. Heuristics change branch order; incorrect bounds can remove the optimum. Alpha-beta prunes adversarial minimax, a distinct setting.

Enumerating exponentially many outputs still takes exponential total work. Generators may reduce peak memory without changing that bound. Handle duplicate branches and restore shared state on early exits.

A worked trace

Subsets of [1,2] include [],[1],[1,2],[2]. Without undoing choices, the second branch incorrectly retains1.

Cost and assumptions

Subsets number2ⁿ and permutations n!; copying outputs adds their lengths to total work.

Executable example

Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.

Python 3

def subsets(a):
    out, path = [], []
    def visit(i):
        if i == len(a): out.append(path.copy()); return
        visit(i+1)
        path.append(a[i]); visit(i+1); path.pop()
    visit(0)
    return out
assert len(subsets([1,2,3])) == 8

TEST YOUR UNDERSTANDING

Your turn

Why is out.append(path) incorrect here?

Reveal the reasoning

Every output shares the same mutable list. Later pops change earlier results. Copy the path for a snapshot.

Take it further

Write down the input contract and the invariant before changing the example.
Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
Derive the cost under the stated model; measure several input sizes and explain discrepancies.

Primary reading & lecture notes

Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.

Jeff Erickson · Algorithms ↗

Solve the exercise before moving on.

RasimAtaberkŞahin