Time Complexity of Backtracking

The honest way to analyze backtracking is number of visited nodes times work per node. The node count comes from the recursion tree. The work per node includes generating choices, checking constraints, copying an answer, marking state, and undoing state.

Many wrong complexity answers ignore copying. If a subset solution records 2^n answers and each recorded list can have length up to n, the output-copying cost is O(2^n * n), not just O(2^n).

Subsets usually have 2^n leaves because every element is included or excluded. With answer copying, the standard bound is O(2^n * n) time and O(n) recursion depth excluding output.

Combinations of size k have C(n, k) answers. A tight output-sensitive bound is often O(C(n, k) * k) when the algorithm records only size-k paths, plus internal loop overhead. In interviews, it is acceptable to state a safe upper bound such as O(2^n * n) when the combination search is a pruned subset tree.

Permutations have n! leaves because the number of choices shrinks from n to 1 across the depth levels. Recording each permutation costs O(n), so the common bound is O(n! * n) time and O(n) auxiliary space excluding output.

The recursion tree also has internal nodes for partial prefixes, but they are dominated by the factorial number of leaves in the usual asymptotic statement. Duplicate pruning can reduce the number of leaves to the number of unique permutations, but the worst case remains factorial when all values are distinct.

Board search bounds depend on the branching factor and depth. Word Search over a word of length m often uses O(rows * cols * 3^m) after the first step because each cell has at most three onward directions when revisiting the parent is forbidden. Sudoku is frequently bounded by O(9^e) where e is the number of empty cells, though constraint checks and choosing the next cell can prune heavily.

String partitioning problems usually branch over cut positions. Palindrome Partitioning can have O(2^n) partitions in the worst case, with additional substring or path-copying cost depending on implementation.

Auxiliary space is usually the recursion depth plus the mutable structures used by one active path. A subset path has length at most n. A permutation has a path and used[], both O(n). A board search may mutate the board in place and use stack depth equal to the length of the path.

Output space is separate and can dominate everything. If the problem asks for all solutions, storing the answers costs the number of answers times the size of each answer.