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.

It is a systematic trial-and-error method of exploring all possibilities to solve computational problems. It builds a solution incrementally and abandons a path ("backtracks") as soon as it determines the path cannot possibly lead to a valid solution. It is also known as control recursion.

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
                = Control Recursion
  

Steps of Backtracking:

The basic steps in backtracking are as follows:

1. Choose: Start with the first option, make a decision, and add it to the current solution.
2. Explore: Recursively proceed with the next choice, trying to complete the solution.
3. 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

1. 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.
2. 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.
3. 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.
4. 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.
5. Small Input Size: Due to the high time complexity (often exponential, such as n!, 2^n, or higher-order polynomial like n^2), backtracking problems typically have small input constraints. The input size n is often limited to a small range, typically single digits, to keep computation feasible.
6. 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:

1. Backtracking vs. Brute Force: While brute force checks all possibilities, backtracking eliminates large subsets of possibilities based on constraints, making it more efficient.
2. 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.
3. 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.

🔍Identification of Backtracking Problem

There is no hard and fast rule for the identification of the backtracking problems. However we have some indicators which are given below for the identification for the backtracking problem:

1. Choices + Decision
2. All Combinations
3. Controlled Recursion
4. Number of choices
5. Size of constraints
6. Don't be greedy

Is it a Backtracking Problem?

Common Keywords That Signal Backtracking

• "Find all..."
• "Generate all combinations/permutations/arrangements"
• "Place objects with constraints"
• "Explore paths"
• "Solve a puzzle"
• "Try all possibilities"
• "Undo previous move"

Red Flags (Probably Not Backtracking)

Generic Backtracking Template (C++)

void backtrack(State currentState, Parameters...) {
    // ✅ 1. Base Case: Is the solution complete?
    if (isSolution(currentState)) {
        processSolution(currentState); // or store it
        return;
    }

    // 🔁 2. Iterate through all candidates at this level
    for (each possible choice at this state) {
        
        // 🚫 3. Prune invalid choices early (optional)
        if (!isValid(choice, currentState)) continue;

        // ✅ 4. Make the choice
        makeChoice(choice, currentState);

        // 🔁 5. Explore further
        backtrack(currentState, Parameters...);

        // 🔙 6. Undo the choice (backtrack)
        undoChoice(choice, currentState);
    }
}

#include <iostream>
#include <vector>
using namespace std;

// Backtracking function
void backtrack(vector<int>& path, vector<bool>& used, int n) {
    // ✅ Base case: if a complete solution is formed
    if (path.size() == n) {
        // Process or print the solution
        for (int num : path) cout << num << " ";
        cout << endl;
        return;
    }

    // 🔁 Try each candidate
    for (int i = 0; i < n; ++i) {
        if (used[i]) continue; // Skip if already used

        // ⛔ Optional: Add pruning logic here if needed

        // ✅ Choose
        used[i] = true;
        path.push_back(i);

        // 🔁 Recurse
        backtrack(path, used, n);

        // 🔄 Unchoose (Backtrack)
        used[i] = false;
        path.pop_back();
    }
}

Khandani Template by MIK

1. Do something
2. Explore
3. Revert Step 1 & further explore

Backtracking Problems

1. Permutations 1 (Generate all permutations) (20100): https://thejat.in/code/permutations
2. Permutations 2 (Generate all permutations with duplicates)(20200): https://thejat.in/code/permutations-2
3. Power Set (Generate all subsets)(20300): https://thejat.in/code/power-set
4. Combinations (20400): https://thejat.in/code/combinations
5. Combination Sum (20500): https://thejat.in/code/combination-sum
6. Combination Sum 2 (20600): https://thejat.in/code/combination-sum-2
7. Combination Sum 3 (20700): https://thejat.in/code/combination-sum-3
8. Letter Combinations of a phone number (20800): https://thejat.in/code/letter-combinations-of-a-phone-number
9. Palindrome partitioning (20900): https://thejat.in/code/palindrome-partitioning
10. Word search (21000): https://thejat.in/code/word-search
11. N-Queen (21100): https://thejat.in/code/n-queen
12. Rat in a maze (21200): https://thejat.in/code/rat-in-a-maze
13. M Coloring Problem (21300): https://thejat.in/code/m-coloring-problem
14. Sudoko Solver (21400): https://thejat.in/code/sudoko-solver.
15. Restore IP Addresses (21500): https://thejat.in/code/restore-ip-addresses
16. Generate Parentheses (21600): https://thejat.in/code/generate-parentheses

LeetCode Problems

• https://leetcode.com/problem-list/backtracking/
• https://www.youtube.com/watch?v=vPClv7kUExE&list=PLICVjZ3X1AcY5ai7at5OvS4ckXiMbWxCa&index=7
• https://www.abhinavpandey.dev/blog/backtracking-algorithms