Backtracking

Concept

Backtracking is an advanced algorithmic technique used to generate all possible combinations or permutations of a dataset.

It is heavily used to solve problems like:

• Generating all valid subsets of [1, 2, 3]
• Finding all valid paths through a maze
• Solving a Sudoku puzzle or the N-Queens problem

The Mechanism:
Backtracking explores a decision tree. You walk down a path, making a choice at every step. If you reach a valid solution, you save it. If you reach a dead end (or an invalid state), you “backtrack”—you undo your last choice, step backward up the tree, and try a different path.

The Mental Model

Imagine picking a 3-digit combination lock using [1, 2, 3].

1. Choose 1. Current path: [1]
2. Choose 2. Current path: [1, 2]
3. Choose 3. Current path: [1, 2, 3]. It’s full! Save [1, 2, 3] to the results.
4. BACKTRACK: Remove 3. Path is [1, 2]. Try another number? None left.
5. BACKTRACK: Remove 2. Path is [1].
6. Try 3 instead! Path is [1, 3].
7. Choose 2. Path is [1, 3, 2]. Save it!
8. …repeat until all possibilities are explored.

The Universal Backtracking Template

Almost every single Backtracking problem on LeetCode can be solved using this exact same boilerplate template. You just change the if conditions.

function solveBacktrackingProblem(nums: number[]): number[][] {
    const result: number[][] = [];
    const currentPath: number[] = [];

    // The recursive DFS engine
    function backtrack(startIndex: number) {
        
        // 1. BASE CASE: Did we reach a valid solution?
        // (e.g., if path length equals target size, save it and return)
        if (currentPath.length === targetSize) {
            // WE MUST CLONE THE ARRAY! [...currentPath]
            result.push([...currentPath]); 
            return;
        }

        // 2. EXPLORE: Loop through the available choices
        for (let i = startIndex; i < nums.length; i++) {
            
            // 3. DO: Make a choice
            currentPath.push(nums[i]);
            
            // 4. RECURSE: Dive deeper into the tree
            backtrack(i + 1);
            
            // 5. UNDO (BACKTRACK): We hit a dead end or finished that branch. 
            // Undo the choice so the loop can try the next number!
            currentPath.pop();
        }
    }

    backtrack(0);
    return result;
}

The Array Cloning Trap

Look at this line: result.push([...currentPath]);

A junior developer will just write result.push(currentPath). This will ruin the entire algorithm.
In JavaScript, Arrays are passed by reference. If you push currentPath into the result, you are pushing a pointer to the array in RAM.
As the recursion continues, the currentPath.pop() line physically mutates that exact same array. By the end of the algorithm, your result array will just be full of completely empty arrays [[], [], []], because the backtracking logic eventually pop()ped everything out of the original array!
You MUST create a frozen, shallow clone [...currentPath] the moment you find a valid solution to preserve it forever.

Time Complexity

Backtracking algorithms are fundamentally Brute Force algorithms. They explore every single mathematical possibility.
Therefore, their time complexities are always astronomically slow:

• Subsets: $O(2^N)$ (Every item is either included or excluded).
• Permutations: $O(N!)$ (N Factorial).

Because they are so slow, LeetCode problems that require Backtracking will always have incredibly small constraints, like $N \le 20$. If a problem has $N = 10,000$, Backtracking is physically impossible, and you must use Dynamic Programming or Greedy approaches.

Interview Questions

Q: In the Sudoku Solver backtracking algorithm, how does the program know when to undo a move?
A: The backtrack function is modified to return a boolean. When it places a number on the board, it recursively calls if (backtrack(nextCell)) return true;. If the recursion hits a dead-end later on (no numbers are valid), it returns false. This false signal bubbles up, triggering the currentPath.pop() (or in Sudoku, board[r][c] = '.') to erase the number and try the next valid digit in the for loop.