Backtracking

Previous: Algorithm, Depth-first search

Backtracking is an algorithmic paradigm that incrementally builds solutions while discarding invalid states.

1. Base case
2. Choices
3. Constraints
4. Backtrack

def backtrack(params):
    if base_case_condition:
        save_result
        return

    for choice in choices:
        if violates_constraints:
            continue

        make_choice
        backtrack(updated_params)
        undo_choice  # Backtracking Step