Recursion & BacktrackingHard

Backtracking

Explore all possibilities by trying choices and undoing them (pruning dead-ends).

How it works

Backtracking is a systematic way to search through all possible configurations by building the solution incrementally. At each step, you make a choice, recurse to explore that path, then undo the choice (backtrack) and try the next option. The key advantage over brute force is pruning: if the current partial solution already violates a constraint, you abandon it immediately without exploring further. The template is always: "for each choice: make choice → recurse → undo choice." Common pruning strategies include checking size limits, constraint violations, and using a visited set to avoid revisiting nodes. The result is collected in an accumulator passed through the recursion.

Interactive Playground

Build solution incrementally. Try first choice: pick A.

Speed

When to use

Generating all permutations or subsets
Constraint satisfaction (N-Queens, Sudoku)
Path finding with constraints

✅Tips

1Pass a mutable "current path" list and a "results" list through the recursion — append to path on choice, pop on undo.

2Sort the input first to make deduplication easier — skip duplicate elements at the same recursion level.

3Prune as early as possible: check constraints before recursing, not after.

4Use a boolean visited[] array for permutations to avoid reusing elements; use a start index for combinations to avoid duplicates.

❌Common Mistakes

!Forgetting to undo the choice after recursion — the path list keeps growing incorrectly.

!Adding a reference to the current path instead of a copy — all results end up pointing to the same (empty) list.

!Not pruning duplicate choices at the same level in the recursion tree — produces duplicate results.

!Confusing permutations (order matters, use visited[]) vs combinations (order doesn't matter, use start index).

💡 Key Insight:"Try → recurse → undo" in a for loop. Prune early to avoid wasted work.

Solved Problems0

No solved problems yet.

Related Patterns

Recursion→