Backtracking Pattern in Java — Subsets, Permutations, N-Queens, Pruning
Fast recall
Quick revision
Core answer
solve(state) { if base case: record; for each choice: apply; solve; undo; }. The 'undo' step is what distinguishes backtracking from plain recursion — we mutate a shared state (list, board, visited set) and restore it after the recursive call, saving memory. Complexity is typically exponential — O(2^n) for subsets, O(n!) for permutations, O(b^d) general (b = branching, d = depth) — but pruning (abandoning branches that can't yield a valid solution) is key to making it practical. Canonical examples: Subsets (2^n) — at each element, choose include or exclude; Permutations (n!) — track a used[] array; Combination sum — try each candidate, with pruning by remaining target; N-queens — try each column in each row, pruning via column/diagonal constraints. Pruning techniques: (1) Invalid state detection — return early if current partial state violates constraints (N-queens: conflicting queen); (2) Bound-based pruning — if best possible from here is worse than current best, abandon (branch-and-bound); (3) Symmetry breaking — avoid equivalent permutations (sort and skip duplicates); (4) Ordering — try promising candidates first to find a valid solution quickly. When to use backtracking: (1) need all solutions or count of solutions; (2) constraint satisfaction; (3) search space is too large for DP but structured enough to prune. Don't use when: greedy works (faster), DP applies (polynomial), or the problem is truly random. Watch out: shared-state mutation requires careful add/remove pairs; forgetting to undo is a classic bug.Whether the candidate can apply the backtracking template, implement canonical examples (subsets, permutations, N-queens, combination sum), and recognize pruning opportunities
Forgetting to undo the state mutation after recursion. Using separate lists per branch (wastes memory). Not pruning, leading to TLE. Forgetting duplicate-handling in combination/subset problems
Explain the template pattern generically, discuss several pruning techniques (invalid state, bound, symmetry, ordering), mention branch-and-bound for optimization variants, and contrast with DP
Interview-ready guide
Interview answer
Backtracking is a brute-force search that explores all possible solutions recursively, making choices and undoing them when a path fails or completes.
The template
- 1If base case (solution complete): record and return
- 2For each choice:
- Check validity (prune if invalid)
- Apply choice (mutate state)
- Recurse
- Undo choice (restore state)
Why 'undo'?
- Avoids copying full state at each call
- Shared mutable state is memory-efficient
- 'Undo' is what distinguishes backtracking from plain recursion
Typical state
- Current path (ArrayList)
- Used flags (boolean[])
- Board state (2D array)
- Visited set
Complexity
- 2^n for subsets
- n! for permutations
- b^d general (branching × depth)
- Pruning is essential to make practical
Canonical problems
Subsets (2^n)
- Each element: include or exclude
- Use
startindex to avoid reusing - Every recursion-tree node is a valid subset (record at entry)
Permutations (n!)
- Try each unused element at each position
- Track with used[] array
- Base case: current.size() == n
Combination sum
- Unlimited reuse: recurse with
i(noti+1) - Sort + early break on target exceeded (pruning)
N-queens
- Place one queen per row, try each column
- Prune: validate column + both diagonals
- Faster: three boolean arrays (cols, diag1, diag2)
Pruning techniques
1. Invalid state detection
- Check constraints before recursing
- N-queens conflict check
2. Bound-based (branch and bound)
- Upper bound on best achievable
- Abandon if can't beat current best
- TSP, exact knapsack
3. Symmetry breaking
- Skip duplicates (subsets/permutations with repeats)
- N-queens: restrict first queen to half board
4. Ordering
- Try promising choices first
- Most-constrained variable heuristic (Sudoku)
- A* search
5. Memoization
- If subproblems overlap: cache
- Sometimes converts backtracking to DP
6. Bitmask state
- Small N: encode 'used' as int bitmask
- Fast copy; enables memoization
- TSP with dp[current][visited]
Duplicate handling
- Sort first
- Skip:
if (i > start && nums[i] == nums[i-1]) continue; - For permutations:
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue; - Ensures canonical order, eliminates duplicates
Common pitfalls
1. Forgetting to undo
current.remove(current.size() - 1)after recursion- Without this: accumulating state across branches — wrong answers
2. Copying separate state per branch
- Wastes memory
- Use shared mutable state with undo
3. Forgetting to copy on record
result.add(current)vsresult.add(new ArrayList<>(current))- First adds reference; later mutations corrupt the recorded answer
- Always copy
4. No pruning
- Time limit exceeded
- Add early returns, bound checks, sort + skip
5. Wrong index passing
- Subsets:
i + 1(no reuse) - Combination sum (unlimited):
i - Permutations: no start index, just used[]
6. Off-by-one in base case
- Subsets: record at every entry (all sizes)
- Permutations: record when size == n
- Combinations: record when we hit target size or sum
When to use backtracking
Good fit
- All solutions or count
- Constraint satisfaction (Sudoku, N-queens)
- Small n, structured pruning
- Tree/graph search with backtrack (word search)
Not a good fit
- Polynomial solution exists (DP, greedy)
- Problem is truly random (no pruning possible)
- Pure optimization with linear structure (greedy)
Backtracking vs DP
- DP: polynomial, overlapping subproblems, optimization
- Backtracking: exponential, combinatorial, all-solutions
- Hybrid: backtracking with memoization (when subproblems overlap)
Backtracking vs BFS/DFS
- DFS without undo: visits once, can't revisit
- Backtracking: revisits after undo (different paths)
- BFS: finds shortest path, different problem class
Branch and bound
- Backtracking + upper/lower bound pruning
- For optimization: TSP, exact 0/1 knapsack
- Uses fractional knapsack as bound
Recommendation: Master the backtracking template — choose, recurse, undo — because it applies to a huge class of combinatorial problems: subsets, permutations, combinations, N-queens, Sudoku, word search, generate parentheses, restore IP addresses. The essence is the 'undo' step; without it, you're doing plain recursion and wasting memory via state copies. Always copy when recording (new ArrayList<>(current)) because the current state mutates. For problems with duplicate elements, sort first and skip duplicates at each level — either if (i > start && nums[i] == nums[i-1]) for subsets/combinations or if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) for permutations. For unlimited reuse (combination sum), recurse with i, not i+1. Pruning is what makes backtracking practical — use invalid state detection (abandon violating branches), bound-based pruning (branch-and-bound for optimization), symmetry breaking (canonical ordering), and smart ordering (most-constrained-variable first). For N-queens, track queens[row] = col and validate columns and both diagonals; use three boolean arrays for O(1) validity. When subproblems overlap, add memoization — backtracking morphs into top-down DP. Don't reach for backtracking when greedy or DP would work faster; backtracking is for when the search space is fundamentally combinatorial and pruning can prevent exponential blow-up. The mental model: backtracking = DFS of the decision tree with state mutation and undo. Master the template, then recognize it everywhere combinatorial search is needed.
Backtracking Pattern in Java — Subsets, Permutations, N-Queens, Pruning
Direct Answer
Backtracking is a brute-force search technique that explores all possible solutions recursively, making choices at each step and undoing them (backtracking) when a path fails or is complete. It's used for combinatorial problems: subsets, permutations, combinations, N-queens, Sudoku, word search, path-finding with constraints. The template: solve(state) { if base case: record; for each choice: apply; solve; undo; }. The 'undo' step is what distinguishes backtracking from plain recursion — we mutate a shared state (list, board, visited set) and restore it after the recursive call, saving memory. Complexity is typically exponential — O(2^n) for subsets, O(n!) for permutations, O(b^d) general (b = branching, d = depth) — but pruning (abandoning branches that can't yield a valid solution) is key to making it practical. Canonical examples: Subsets (2^n) — at each element, choose include or exclude; Permutations (n!) — track a used[] array; Combination sum — try each candidate, with pruning by remaining target; N-queens — try each column in each row, pruning via column/diagonal constraints. Pruning techniques: (1) Invalid state detection — return early if current partial state violates constraints (N-queens: conflicting queen); (2) Bound-based pruning — if best possible from here is worse than current best, abandon (branch-and-bound); (3) Symmetry breaking — avoid equivalent permutations (sort and skip duplicates); (4) Ordering — try promising candidates first to find a valid solution quickly. When to use backtracking: (1) need all solutions or count of solutions; (2) constraint satisfaction; (3) search space is too large for DP but structured enough to prune. Don't use when: greedy works (faster), DP applies (polynomial), or the problem is truly random. Watch out: shared-state mutation requires careful add/remove pairs; forgetting to undo is a classic bug.
Common Mistakes & Pitfalls
Forgetting to undo the state mutation after recursion. Using separate lists per branch (wastes memory). Not pruning, leading to TLE. Forgetting duplicate-handling in combination/subset problems
Check your understanding
Answer these without looking back at the article.
- How does backtracking differ from plain recursion or DFS?
- How do you handle duplicates in subsets and permutations problems?
- What's branch-and-bound and when does it apply?
- How can backtracking be combined with memoization?
- Why is pruning essential for N-queens and Sudoku?
Related interview prep categories
1Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.