Backtracking Algorithm: Concepts, Core Ideas, General Steps, and Frameworks

Backtracking is an enumeration‑style search process that explores a problem’s solution space and retreats to previous states when current choices violate constraints, effectively performing a depth‑first search with systematic backtracking.

The core idea is to traverse the solution‑space tree depth‑first from the root, checking each node for a valid solution; if a node fails, the algorithm backtracks to its ancestor to try alternative paths.

Typical problem‑solving steps include: (1) clearly define the solution space so it contains at least one valid solution, (2) establish expansion rules for nodes, and (3) conduct a depth‑first search while applying pruning functions to eliminate futile branches.

In a typical formulation, a problem’s solution is represented as an n‑dimensional vector (a1, a2, …, an) with constraints f(ai). The following non‑recursive pseudo‑code demonstrates the backtracking framework:

int a[n], i;
// initialize array a[]
i = 1;
while (i > 0 && not reached goal) {
    if (i > n) {
        // found a solution, output
    } else {
        // process element i
        a[i] = first possible value;
        while (a[i] violates constraints && within search space) {
            a[i] = next possible value;
        }
        if (a[i] within search space) {
            // occupy resources
            i = i + 1; // expand to next node
        } else {
            // clean occupied state space // backtrack
            i = i - 1;
        }
    }
}

The recursive version leverages the call stack to simplify backtracking, as shown below:

int a[n];
void try(int i) {
    if (i > n) {
        // output result
    } else {
        for (j = lower; j <= upper; j++) {
            if (fun(j)) { // satisfies bound and constraints
                a[i] = j;
                // other operations
                try(i + 1);
                // cleanup before backtrack (e.g., a[i] = null)
            }
        }
    }
}