All Patterns
🔙
hardPattern #08
Backtracking
Explore all possibilities by building candidates and pruning dead ends.
What is this pattern?
Backtracking incrementally builds a solution and abandons a path ("backtracks") as soon as it determines the path cannot lead to a valid answer. It is a systematic brute-force with early pruning — essential for combinatorial problems.
When to use it
- Generating all subsets, permutations, or combinations
- Grid/string problems asking to "find all valid paths"
- Constraint satisfaction (N-Queens, Sudoku)
- Keywords: "all possible", "generate all", "find all combinations"
Key Insight
The pattern is always: choose → recurse → unchoose. The "unchoose" step (removing the last element from your path) is what makes backtracking distinct from plain DFS. Always pass a start index to avoid re-using elements.
Pro Content
The Java template and practice problems for this pattern are part of the Pro plan. Upgrade to unlock all patterns, 500+ problems, and Aria code reviews.
From ₹3,999 for a year · one-time, no auto-renewal