ReviseAlgo Logo

Backtracking

Practice & Revision

Backtracking recursion decision tree, cheat sheet, and Top 15 must-solve backtracking interview problems.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

This section serves as your comprehensive reference and practice guide for Backtracking algorithms. Master these templates, review the decision tree, and solve the curated Top 15 interview problems to prepare for technical interviews.

2. Backtracking Decision Tree

Use this flow chart to determine the correct backtracking template based on your problem:

3. Revision Cheat Sheet

Backtracking De-duplication Templates Comparison

4. Top 15 Must-Solve Backtracking Problems

Note: Interactive Practice Table Available: Switch to the Practice Problems tab at the top of this lesson to interactively solve, track completion, watch video solutions, and take notes on all 15 must-solve backtracking interview problems!

5. Problem-Solving Framework

When coding backtracking solutions, follow this 3-step checklist:

1. Always Clone Final Path References: - Remember: lists are passed by reference in Java, Python, and C++ (if using pointers). When adding path to the final results list, always create a deep copy (e.g., results.append(list(path)) in Python). 2. Sort Inputs to Enable Pruning: - If sum parameters or values can exceed targets, sorting the array lets you break the loop early, pruning the remaining subtrees and saving search cycles. 3. Verify Restored Global States: - Run a mental trace: for every push/mark operation, check if there is a matching pop/unmark operation. Corrupted global arrays will lead to incorrect outputs.

6. Quiz

Question 1: What is the time complexity of 'Combination Sum' where elements can be reused multiple times? Answer: O(2^T) where T is the target sum divided by the smallest element. The depth of the recursion tree can reach T levels, and we branch binary choice steps (take vs skip) at each level.
Question 2: In 'Permutations II', what is the significance of the !used[i-1] condition when nums[i] == nums[i-1]? Answer: It enforces a fixed relative order of duplicate elements. If the previous identical element is not yet used, we skip placing the current one, preventing identical arrangements from being generated.
Question 3: Why does 'Word Search II' use a Trie instead of a flat set of words? Answer: A Trie allows us to check if the current cell path is a valid prefix of any dictionary word in O(1) time. If it is not a valid prefix, we backtrack immediately, pruning millions of grid search cycles.
Question 4: True or False: If we use backtracking to solve the N-Queens problem, the search space is exactly O(N^N). Answer: False. Because we prune the search space by placing at most one queen per row and column, the search space is bounded by O(N!), which is significantly smaller than O(N^N).
Question 5: What is the benefit of using arrays instead of hash sets to track threatened columns and diagonals in N-Queens? Answer: Boolean arrays (e.g. boolean[] cols = new boolean[n]) avoid hashing collisions and overhead, performing slightly faster in practice than HashSets.