← All Comparisons
Backtracking vs DFS
Quick Answer
Use DFS when you only need to explore or find a single path (e.g., path exists, connected components, cycle detection). Use Backtracking when you must enumerate all valid solutions and need to undo choices to try alternatives (e.g., all permutations, all combinations, N-Queens).
Side-by-Side Comparison
| Aspect | DFS | Backtracking |
|---|---|---|
| Core mechanism | Explore and move forward only | Explore, then undo to try alternatives |
| State modification | Usually immutable or copy-on-write | Mutate state, then restore on backtrack |
| Goal | Find one path, detect cycle, count components | Enumerate all valid solutions |
| Typical problems | Path exists, number of islands, cycle detection | All permutations, subsets, N-Queens, Sudoku |
| Early termination | Often yes (stop when target found) | Usually no (must explore all branches) |
| Constraint handling | Prune invalid branches; no undo needed | Prune and undo to try other valid choices |
| Implementation | Visit, recurse, return; no explicit undo | Choose, recurse, undo (pop/restore), try next |
Decision Framework
- Does the problem ask for "all" solutions (all paths, all combinations, all permutations)? Use Backtracking.
- Does the problem ask "does a path exist" or "how many components"? Plain DFS is enough.
- Do you need to share mutable state across branches (e.g., a board, a path array)? Use Backtracking with undo.
- Can you pass state forward as copies (e.g., path + [node])? DFS without backtracking may suffice.
- Is it a constraint satisfaction problem (N-Queens, Sudoku)? Backtracking with place-and-undo.
- Is it a graph/tree traversal with no need to enumerate all valid configurations? Use DFS.
Example Problems
DFS (no backtracking needed)
- 1.Number of Islands — Flood fill; mark visited, no need to undo.
- 2.Path Sum — Check if any root-to-leaf path sums to target; pass sum forward.
- 3.Course Schedule — Cycle detection; no enumeration of all valid orderings.
- 4.Max Area of Island — Count cells in each component; no undo.
Backtracking (undo required)
- 1.Permutations — Enumerate all orderings; swap, recurse, swap back.
- 2.Subsets — Include/exclude each element; push, recurse, pop.
- 3.N-Queens — Place queen, recurse, remove queen to try next column.
- 4.Word Search — Mark cell, recurse, unmark to allow reuse in other paths.