> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/backtracking.md).

# Backtracking

**It's a clever problem-solving strategy that involves exploring possible solutions by building them incrementally, and then, if a solution path doesn't work out, systematically "unbuilding" it to try other paths, like carefully retracing your steps in a maze.**

**Key characteristics:**

* **Recursive approach:** It often uses recursion to explore different branches of potential solutions.
* **Trial and error:** It involves trying different possibilities and backtracking if they don't lead to a valid solution.
* **Pruning:** It can sometimes optimize the search by cutting off branches that clearly won't lead to a solution, saving time and effort.

**Common examples:**

* **Solving Sudoku puzzles:** Filling the grid with numbers while satisfying constraints.
* **N-Queens problem:** Placing N queens on a chessboard so that none attack each other.
* **Maze solving:** Finding a path from start to finish in a maze.
* **Generating permutations and combinations:** Producing all possible arrangements of items.

**When to consider backtracking:**

* Problems that involve finding a combination of choices that satisfy certain constraints.
* Problems where the solution space is large or complex, and you need to explore it systematically.
* Problems where you can easily check if a partial solution is valid or not.