Skip to main content

Backtracking

Backtracking algorithms are a type of exhaustive search technique used to solve problems. The core approach involves starting from an initial state and exploring all possible solutions by trying each choice once. Only correct solutions are recorded, and the search continues until a solution is found or all choices are tried. This method utilizes depth-first search to traverse the solution space.

Trying and Retreating​

Backtracking is characterized by a "try" and "retreat" method. As solutions are explored:

  • A "try" is made at each node of the search space.
  • A "retreat" occurs when a dead-end is reached or the solution space needs to be exited, reverting to a previous state to explore alternate paths.

Example One: Pre-order Traversal​

In a binary tree, to find all nodes with a specific value (e.g., 7), pre-order traversal is used:

def pre_order(root: TreeNode):
    if root is None:
        return
    if root.val == 7:
        res.append(root)
    pre_order(root.left)
    pre_order(root.right)

Example Two: Tracking Paths​

To find all paths leading to nodes with a specific value, modify the traversal to include a path tracker:

def pre_order(root: TreeNode, path, res):
    if root is None:
        return
    path.append(root)
    if root.val == 7:
        res.append(list(path))
    pre_order(root.left, path, res)
    pre_order(root.right, path, res)
    path.pop()

Pruning​

Pruning is employed to improve efficiency by eliminating paths that do not lead to a solution early in the search process.

Example Three: Pruning Specific Values​

In a tree, to find all paths to nodes with a value of 7, excluding paths containing nodes with a value of 3:

def pre_order(root: TreeNode, path, res):
    if root is None or root.val == 3:
        return
    path.append(root)
    if root.val == 7:
        res.append(list(path))
    pre_order(root.left, path, res)
    pre_order (root. right, path, res)
    path.pop ()

Framework for Backtracking​

A generalized framework for backtracking includes:

  1. Checking if the current state is a solution.
  2. Recording the solution and halting the search if necessary.
  3. Iterating through all possible choices, applying pruning and trying new states recursively.
def backtrack (state, choices, res):
    if is_solution (state):
        record_solution (state, res)
        return
    for choice in choices:
        if is_valid (state, choice):
            make_choice (state, choice)
            backtrack (state, choices, res)
            undo_choice (state, choice)

Common Terminology in Backtracking​

  • Solution: A valid answer that satisfies the problem conditions.
  • Constraint: Conditions that limit the feasibility of solutions.
  • State: The current condition or setup of the problem, including made choices.
  • Attempt: The exploration of the solution space.
  • Backtracking: Undoing choices to return to a prior state.
  • Pruning: Avoiding unnecessary paths in the solution space to enhance efficiency.

Advantages and Limitations​

  • Advantages: Can find all possible solutions; efficient with appropriate pruning.
  • Limitations: Potentially high time and space complexity, especially with complex or large-scale problems.

Typical Problems Solved Using Backtracking​

  • Search problems: Full permutations, subset sum problem, Tower of Hanoi.
  • Constraint satisfaction problems: n-queens, Sudoku, graph coloring.
  • Combinatorial optimization problems: 0-1 knapsack, traveling salesman, maximum clique.