Backtracking is a general algorithmic technique that involves exploring all possible solutions by incrementally building candidates and abandoning a candidate ("backtracking") as soon as it determines that the candidate cannot lead to a valid solution. This technique is particularly useful for solving problems that involve searching for a combination or permutation of elements, such as puzzles, constraint satisfaction problems, and combinatorial optimization problems.

Process

1. Initialization: Start by defining the problem space and initializing the candidate solution.

2. Recursive Exploration: Recursively explore each possible choice or move that can be made from the current state.

3. Constraint Checking: At each step, check if the current candidate satisfies all the problem constraints. If it does, continue exploring further choices.

4. Backtracking: If the current candidate does not satisfy the constraints or leads to an invalid solution, backtrack to the previous state and explore other possible choices.

5. Termination: The process terminates when all possible solutions have been explored or when a valid solution is found.

When to Use

1. Combinatorial Problems: To solve problems that involve finding combinations or permutations of elements.

2. Constraint Satisfaction Problems: To solve problems where the goal is to find a solution that satisfies a set of constraints.

3. Puzzles and Games: Solve puzzles like Sudoku, N-Queens, and the Knight's Tour.

How Does It Reduce Time Complexity?

1. Prune Invalid Paths: By abandoning invalid candidates early, backtracking reduces the number of unnecessary computations, effectively pruning the search space.

2. Exhaustive Search: Despite being an exhaustive search technique, backtracking can be more efficient than brute force methods by avoiding exploring paths that cannot lead to a solution.

Example problems for better understanding

Subsets

Combination Sum

Thank you for reading!

You can support me by buying me a book.