Backtracking

A subset of Complete Search

Idea

Backtracking uses a decision-tree based philosophy, where in one branch, we make a decision, and in the other binary branch, we do something different

Identification

Use for:

• Constraint satisfaction problems, when you need to build a solution step-by-step and satisfy certain conditions.
• Search problems (large solution space but invalid branches can be pruned early)
• Multiple solutions (Explore all possible valid solutions)
• Generate all valid combinations or permutations under constraints

Don’t confuse with Dynamic Programming which can be used to solve problems without overkilling. If there is a single optimal solution, DP might be better.

Has two parts:

• Backtracking
• Pruning the search

Backtracking starts with an empty solution and extends the solution step by step.

Steps to Solve

• Define decision space
• Define what a state means
• Decide how to recursively move forward with this choice
• Check if the state is invalid
  • Determine constraints (when do we prune?)
  • If true, backtrack
• Determine goal condition
• Repeat until all possibilities are explored, or a solution is found

A mental model

Each look iteration should start using the same prefix, use a fresh DS per branch and don’t reuse it for siblings

From ChatGPT…

Backtracking(path):
    if goal(path):
        record path
        return
    
    # This is choosing what element comes next
    for choice in choices:
        apply(choice)
        if is_valid(path):
            Backtracking(path)
        undo(choice)

^^ Make sure to follow this model rather than the Dynamic Programming take / leave choice model which will lead to a 2^n solution. Doing it this way leads to a wider tree. Anything we skip over in the for loop here is implicitly a “leave” choice.