Backtracking

Intro

Backtracking is a powerful programming technique. The main point is to systematically explore the solution spaces by making choices, and undo them in case they do not lead to valid solutions.

Coding Template:

Here is a code template for a typical backtrack problem:

def backtrack(current_state, remaining_choices):
    # Base case: found a complete solution
    if is_complete(current_state):
        process_solution(current_state)
        return
    
    # Try each possible choice
    for choice in get_valid_choices(remaining_choices):
        # Make the choice
        make_choice(current_state, choice)
        
        # Recurse
        backtrack(current_state, updated_remaining_choices)
        
        # Undo the choice (backtrack)
        undo_choice(current_state, choice)

if __name__==__main__
    setup_solution_collection()
    backtrack(initial_state_,all_choices)
    return solution

Examples:

The N-Queens problem

LeetCode