Ever faced a problem where you need to try all possible solutions… but don’t know how?
That’s where Backtracking comes in.
What is Backtracking?
Backtracking is a technique where you:
- Try a solution
- If it fails → go back
- Try another path
It’s like solving a maze:
- Take a path
- Hit a dead end
- Go back and try another route
Where is Backtracking Used?
- N-Queens problem
- Sudoku solver
- Generating subsets
- Permutations & combinations
- Rat in a maze
General Backtracking Template
void backtrack(parameters) {
if (solution found) {
process solution;
return;
}
for (int candidate : candidates) {
if (isValid(candidate)) {
makeChoice(candidate);
backtrack(updatedParameters);
undoChoice(candidate); // backtrack
}
}
}
Example: Generate All Subsets
void subsets(int[] nums, int index, List current, List> result) {
result.add(new ArrayList<>(current));
for (int i = index; i < nums.length; i++) {
current.add(nums[i]);
subsets(nums, i + 1, current, result);
current.remove(current.size() - 1); // backtrack
}
}
Key Idea
Backtracking works in 3 steps:
- Choose
- Explore
- Undo (Backtrack)
This ensures all possibilities are explored.
Important Note
- Time complexity is often exponential
- But pruning (skipping invalid paths early) improves performance
For More: https://www.quipoin.com/tutorial/data-structure-with-java/backtracking-basics
