When to Use Backtracking
Use backtracking when a problem asks you to construct configurations through sequential choices under constraints, especially when it needs all solutions or any valid arrangement.
Strong Signals
Backtracking is a strong candidate when the prompt says generate all, return all valid, find any arrangement, place items, partition a string, choose k, or try every assignment under constraints. These phrases imply a search over configurations rather than a single linear pass.
Small input limits are another signal. If n <= 10, n <= 15, a board has a limited number of empty cells, or the prompt asks for all outputs, an exponential or factorial search may be intended.
Construct by Choices
Backtracking fits when a solution can be built one decision at a time and invalid partial decisions can be rejected early. Subsets choose take or skip. Permutations choose which unused value fills the next position. Combinations choose the next index. String partitioning chooses the next cut. Board problems choose the next placement or move.
If you can clearly name the current partial candidate and the legal next choices, the choose, explore, unchoose template is probably close to the final solution.
When Another Tool Is Better
Use DP when many different histories collapse into the same subproblem and the goal is a count, minimum, maximum, or feasibility answer rather than listing distinct configurations. Backtracking explores histories; DP merges equivalent states.
Use greedy when a local choice can be proven safe and there is no need to revisit alternatives. Use BFS when the problem asks for the shortest number of moves in an unweighted state graph. Use plain DFS graph traversal when you are visiting existing graph nodes rather than constructing candidate objects through reversible choices.
The Interview Decision Process
Before coding, ask four questions: Do I need all solutions or one valid arrangement? Can I build a partial answer one choice at a time? Can I reject invalid partial answers before completion? Are the constraints small enough for exponential search after pruning?
If the answers point to backtracking, explain the state, choices, base case, and pruning before writing code. That framing shows you are controlling the search tree instead of hoping recursion works by magic.
Generate valid parentheses by choices
The solution constructs strings by legal next choices. It prunes any prefix that would use too many closing parentheses.
Key Takeaways
- Backtracking is appropriate when solutions are configurations built through sequential reversible choices.
- Prompts asking for all valid outputs or any valid arrangement often point to search over a decision tree.
- Prefer DP when equivalent histories should merge, greedy when one provably safe choice is enough, and BFS for shortest unweighted paths.
- A strong interview setup names the state, choices, base case, and pruning before code.