What is backtracking in algorithm design?
Backtracking is an algorithm design technique that constructs a solution incrementally, explores each valid choice, and abandons partial solutions that cannot lead to a valid answer. It is especially useful for constraint-based problems such as permutations, combinations, N-Queens, Sudoku, and word search.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Idea
Backtracking follows a choose / explore / un-choose pattern:
-
Choose: Add a valid option to the current partial solution.
-
Explore: Recursively investigate completions that include that option.
-
Un-choose: Remove the option and restore the previous state before trying the next branch.
The main state usually contains:
-
Current path: The partial solution being constructed.
-
Choice state: Information such as a
usedset or indexes already selected. -
Constraints: Conditions that each candidate must satisfy.
-
Base case: The condition that identifies a complete solution, such as every position being filled.
A branch can be pruned when a constraint proves that it cannot produce a valid completion. Pruning is safe because every solution extending that branch would violate the same constraint.
Pruning and Example
For permutations of [1, 2]:
-
Choose
1, making the current path[1]. -
Explore that branch by choosing
2, producing the complete permutation[1, 2]. -
Un-choose
2and then1, restoring the empty path. -
Choose
2and explore it by choosing1, producing[2, 1]. -
Un-choose
1and2after recording the result.
For duplicate values, equivalent branches can be pruned at the same recursion depth so that equal values are treated as indistinguishable. A typical implementation sorts a copy of the input and uses a used_indices set to select candidates without repeating an index.
Other important edge cases include:
-
Empty input: A permutation generator commonly returns one empty permutation,
[[]]. -
One element: It produces one permutation.
-
Duplicates: They may represent indistinguishable values or distinct items, depending on the problem.
-
Negative numbers: They are handled like other sortable values.
-
Already sorted input: It does not change the set of permutations.
-
Cycles and disconnected graphs: Graph searches normally require a
visitedset to prevent repeated visits.
Complexity
Backtracking complexity depends on the search space and the amount of pruning.
-
Exhaustive permutations of
ndistinct values: Best, average, and worst-case time are allO(n × n!), because there aren!permutations and copying each result takesO(n). -
Search size: Permutation enumeration has
O(n!)raw recursive states andO(n × n!)overall search-and-result size when each completed permutation containsnvalues. Subsets commonly haveO(n × 2^n)search-and-result size. -
Constrained problems: Best-case time can be substantially lower when strong pruning finds a solution quickly, while worst-case time remains exponential or factorial.
-
Auxiliary space: Typically
O(d + s), wheredis the recursion depth andsis the size of per-level tracking state; the recursion stack is included. For permutation generation, this isO(n). The input itself is not counted unless the algorithm mutates it. -
Result storage: Exhaustive permutation generation requires
O(n × n!)space when all results are retained.
These bounds are exponential or worse and are not polynomial in the general case.
Common Pitfalls and Interview Tips
-
Forgetting to un-choose: Always restore the path and choice state after exploring a branch.
-
Incorrect base case: Define exactly when a partial solution is complete.
-
Unsafe pruning: Prune only when the constraint guarantees that no valid completion exists.
-
Storing mutable paths directly: Copy each completed path before appending it to the results.
-
Mutating the input: Preserve it unless modification is part of the contract.
-
Ignoring duplicate handling: Decide whether equal values are distinguishable.
-
Recursion depth: Large inputs may exceed Python’s default recursion limit; use an explicit stack or raise the limit deliberately.
-
Graph traversal mistakes: Use a
visitedset for cycles and disconnected components. -
Off-by-one errors: Check depth, index, and completion conditions carefully.
-
Other languages: Account for possible integer overflow when computing sizes or combinatorial values.
Interviewers commonly ask which state must be restored, how pruning improves the worst case, how duplicates are handled, and whether the recursion depth could exceed the language’s limit.