What is Backtracking?
Backtracking is a depth-first search (DFS) approach to problem-solving where we try to build a solution piece by piece. Whenever we reach a point where the solution seems invalid or a dead end, we "backtrack" (i.e., revert our last step) to try another path.
Core Idea: Explore potential solutions incrementally, and abandon a solution path as soon as we determine that it cannot lead to a valid solution. This "abandonment" is what differentiates backtracking from brute force, which would explore all possibilities.
Recursion
|
|
+---------------------------+---------------------------+
Dynamic Programming Backtracking Divide & Conquer
DP = Recursion + Memory (Involves Optimal Solution)
Backtracking = Recursion + Control (All Combinations) + Sometimes Pass
Reference
Steps of Backtracking:
The basic steps in backtracking are as follows:
- Choose: Start with the first option, make a decision, and add it to the current solution.
- Explore: Recursively proceed with the next choice, trying to complete the solution.
- Unchoose/Backtrack: If the current solution path leads to an invalid or complete solution, backtrack by removing the last choice and try the next option.
The recursive structure makes it easy to explore all possibilities by handling each possible choice one step at a time.
Identify Backtracking Problems
- Underlying Recursion Structure: A backtracking problem typically revolves around recursive exploration, where you have multiple choices at each step and must make a decision about which path to explore. The recursive calls are structured to systematically try out all possibilities, backtrack when a choice fails, and then try the next option.
Choices + Decision. - Generating All Possible Combinations: Many backtracking problems require exploring all possible combinations or arrangements of a set of elements. This exhaustive search ensures that every potential solution is considered, making backtracking suitable for problems where multiple solutions must be checked.
- Controlled Recursion: In backtracking, recursion is highly controlled. At each recursive call, constraints are checked to decide whether to proceed further or backtrack. The algorithm ensures that only valid solutions are explored, reducing unnecessary computation.
- Large Number of Choices: The number of choices at each step is generally large and can sometimes vary dynamically based on previous decisions. Number of choices large comparatively recursion, sometimes variable.
- Small Input Size: Due to the high time complexity (often exponential, such as
n!,2^n, or higher-order polynomial liken^2), backtracking problems typically havesmall input constraints. The input sizenis often limited to a small range, typically single digits, to keep computation feasible. - Avoiding Greedy Solutions: Backtracking problems generally cannot be solved using greedy algorithms, as a greedy approach may miss the optimal solution. The exhaustive nature of backtracking ensures that all potential solutions are explored, making it necessary when the problem demands an exhaustive search to find the correct answer.
Backtracking vs. Other Techniques:
- Backtracking vs. Brute Force: While brute force checks all possibilities, backtracking eliminates large subsets of possibilities based on constraints, making it more efficient.
- Backtracking vs. Dynamic Programming: Dynamic programming is used for problems where overlapping subproblems can be optimized using memoization. Backtracking does not usually involve overlapping subproblems.
- Backtracking vs. Greedy Algorithms: Greedy algorithms make local optimal choices at each step, whereas backtracking explores all possible choices but prunes those that don't work.