State Space Search

A state is the complete information needed to continue the search correctly. For subsets, the state may be the current index and path. For permutations, it may be the path plus a used[] array. For N-Queens, it may be the current row plus columns and diagonals already occupied.

The state should include everything that changes the future and exclude history that no longer matters. If two different histories lead to the same remaining possibilities, the state can represent them the same way. If a missing detail changes which choices are legal, the state is incomplete.

The choices are the outgoing edges from the current state. They must be generated according to the problem's rules: unused values for permutations, later indices for combinations, safe cells for a board, or valid cut points in a string.

A strong backtracking solution does not blindly try every imaginable action. It narrows the choice list to actions that are meaningful from the current state, then uses pruning checks to avoid actions that cannot succeed.

The goal or base case says when the search should stop descending. Sometimes completion means record the current candidate, such as a subset or permutation. Sometimes it means return true immediately, such as finding any word path in a grid. Sometimes it means compare a score against the best answer found so far.

Invalid states also stop the search, but they do not become answers. Examples include stepping outside a board, reusing a cell, exceeding a target with positive numbers, or placing an item that violates a constraint.

The full state space can be enormous, but backtracking usually stores only the active path through it. The recursion stack has one frame per depth level, and shared structures such as path, used[], or a board are mutated and restored as the DFS moves.

That is why auxiliary memory is often O(depth) plus the structures needed to represent one state. The output itself can be much larger when the problem asks for all solutions, and that output space is normally counted separately.