Backtracking

Q: What are the most common mistakes with Backtracking?

Forgetting to undo the choice. Adding the shared path itself to the results instead of a copy. Not pruning. Producing duplicates with repeated input values.

Backtracking builds a solution step by step, tries each choice, and undoes it (backtracks) when it leads to a dead end.

🔎 Unravel this example Prerequisites (1)

Learn these first

Recursion

At a glance

Mental model

Walking a maze with chalk: at each fork try a path, and if you hit a wall return to the fork, rub out the chalk mark and try the next path.

What happens, in order

1Pattern: void backtrack(List<Integer> path) { if (path is a full solution) { result.add(new ArrayList<>(path)); return; } for (choice : options) { if (!valid(choice)) continue; path.add(choice); backtrack(path); path.remove(path.size() - 1); } }
2The three steps are choose, explore (recurse) and un-choose (undo), and the undo is what lets one shared path serve every branch
3Save a copy of the path when you find a solution (new ArrayList<>(path)), or later changes will modify the saved result
4Prune early: check validity before recursing (a queen under attack, a sum already too large) so impossible branches are never explored

Remember

The search space is exponential (n!
To avoid duplicate results with repeated values, sort the input and skip equal neighbours at the same depth
The recursion explores a decision tree depth first

Watch out

Forgetting to undo the choiceAdding the shared path itself to the results instead of a copyNot pruningProducing duplicates with repeated input values

Example (highlighted lines explain it)

import java.util.*;public class Permutations {  static List<List<Integer>> permute(int[] nums) {    List<List<Integer>> result = new ArrayList<>();    backtrack(nums, new ArrayList<>(), new boolean[nums.length], result);    return result;  }  private static void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {    if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; }    for (int i = 0; i < nums.length; i++) {      if (used[i]) continue;      used[i] = true; path.add(nums[i]);      backtrack(nums, path, used, result);      path.remove(path.size() - 1); used[i] = false;    }  }}

Read the full explanation (about 1 min)

Backtracking builds a solution step by step, tries each choice, and undoes it (backtracks) when it leads to a dead end. It generates permutations, subsets, N-Queens and Sudoku solutions.

A mental model

Walking a maze with chalk: at each fork try a path, and if you hit a wall return to the fork, rub out the chalk mark and try the next path.

How it works

Pattern: void backtrack(List<Integer> path) { if (path is a full solution) { result.add(new ArrayList<>(path)); return; } for (choice : options) { if (!valid(choice)) continue; path.add(choice); backtrack(path); path.remove(path.size() - 1); } }.

The three steps are choose, explore (recurse) and un-choose (undo), and the undo is what lets one shared path serve every branch.

Save a copy of the path when you find a solution (new ArrayList<>(path)), or later changes will modify the saved result.

Prune early: check validity before recursing (a queen under attack, a sum already too large) so impossible branches are never explored.

Going deeper

The search space is exponential (n! permutations, 2ⁿ subsets); pruning makes hard problems feasible but the worst case stays exponential. Add memoisation if the same state repeats (then it becomes dynamic programming).

To avoid duplicate results with repeated values, sort the input and skip equal neighbours at the same depth.

Recursion depth equals the number of decisions, usually small, so stack overflow is rare here.

Under the hood

The recursion explores a decision tree depth first. Every path.add and path.remove is paired, so the shared list is back to its previous state when the call returns.

Common mistakes

Forgetting to undo the choice.
Adding the shared path itself to the results instead of a copy.
Not pruning.
Producing duplicates with repeated input values.

How Unravel recognises it

When you paste code, Unravel looks for these signs of backtracking. Spotting them yourself is a good habit when you read unfamiliar code:

Method names you declare: backtrack() permute() subsets() permutations() combinations() solveNQueens() generateParenthesis() combine() solveSudoku()
Language constructs: recursion

Part of a learning path

Algorithms and data structures · previous: Graphs: BFS and DFS

Related concepts

RecursionJava language Dynamic programming and memoisationJava language Time complexity (Big O)Java language

Frequently asked questions

What is Backtracking?

Backtracking builds a solution step by step, tries each choice, and undoes it (backtracks) when it leads to a dead end. It generates permutations, subsets, N-Queens and Sudoku solutions.

What are the most common mistakes with Backtracking?

Forgetting to undo the choice. Adding the shared path itself to the results instead of a copy. Not pruning. Producing duplicates with repeated input values.

How can I see Backtracking in real code?

Paste your own Java into Unravel and it will point out where backtracking appears, explain how it works at the detail level you choose, and draw the flow of the code around it.