🔙 JavaScript Backtracking

Parent: Recursion & Backtracking Index

---

What is Backtracking?

Backtracking = Recursion + Undo. Explore every possible path in a decision tree, and when a path fails, undo the last step and try another.

Think of it like solving a maze:
→ Move forward
→ Hit a wall? Go back (backtrack)
→ Try another direction
→ Repeat until you reach the exit

The Universal Template

function backtrack(result, current, /* state */) {
    // 1. BASE CASE: found complete valid solution
    if (isComplete()) {
        result.push([...current]);  // save a COPY
        return;
    }

    // 2. Try every available choice
    for (const choice of getChoices()) {
        if (!isValid(choice)) continue; // prune invalid choices

        // 3. CHOOSE
        current.push(choice);

        // 4. EXPLORE
        backtrack(result, current, /* updated state */);

        // 5. UN-CHOOSE (backtrack)
        current.pop();
    }
}

Critical: Always push [...current] (spread/copy), never push current directly — it will be mutated later.

---

Q1. N-Queens Problem

Problem: Place N queens on N×N board so no two attack each other.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

One queen per row. For each column, check column + both diagonals. Backtrack if unsafe.

Step 2 — Safety tracking:

Track used columns, diagonals (row-col) and anti-diagonals (row+col) in Sets.

Step 3 — Algorithm:

1. For row 0..n-1: for each col, if (col, diag, antiDiag) all free → place queen → recurse → remove

2. Base case: row == n → push solution

function solveNQueens(n) {
    const result = [];
    const cols   = new Set();
    const diag1  = new Set(); // row - col
    const diag2  = new Set(); // row + col
    const board  = Array.from({ length: n }, () => Array(n).fill('.'));

    function backtrack(row) {
        if (row === n) {
            result.push(board.map(r => r.join('')));
            return;
        }

        for (let col = 0; col < n; col++) {
            if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;

            // CHOOSE
            board[row][col] = 'Q';
            cols.add(col);
            diag1.add(row - col);
            diag2.add(row + col);

            // EXPLORE
            backtrack(row + 1);

            // UN-CHOOSE
            board[row][col] = '.';
            cols.delete(col);
            diag1.delete(row - col);
            diag2.delete(row + col);
        }
    }

    backtrack(0);
    return result;
}

console.log(solveNQueens(4).length); // 2
console.log(solveNQueens(8).length); // 92

Time: O(n!) | Space: O(n)

---

Q2. Sudoku Solver

Problem: Fill a 9×9 Sudoku. Empty cells marked '.'.

---

🧠 How to Approach This

Step 1: Find empty cell. Try digits 1-9. Validate row/col/box. Recurse. If stuck, restore '.'.

Step 2 — Box index: boxRow = Math.floor(r/3)3, boxCol = Math.floor(c/3)3

function solveSudoku(board) {
    function isValid(r, c, ch) {
        for (let i = 0; i < 9; i++) {
            if (board[r][i] === ch) return false; // row
            if (board[i][c] === ch) return false; // col
            // 3x3 box
            const br = Math.floor(r / 3) * 3 + Math.floor(i / 3);
            const bc = Math.floor(c / 3) * 3 + (i % 3);
            if (board[br][bc] === ch) return false;
        }
        return true;
    }

    function solve() {
        for (let r = 0; r < 9; r++) {
            for (let c = 0; c < 9; c++) {
                if (board[r][c] !== '.') continue;

                for (let d = 1; d <= 9; d++) {
                    const ch = String(d);
                    if (isValid(r, c, ch)) {
                        board[r][c] = ch;           // CHOOSE
                        if (solve()) return true;    // EXPLORE
                        board[r][c] = '.';           // UN-CHOOSE
                    }
                }
                return false; // No digit worked
            }
        }
        return true; // All cells filled
    }

    solve();
}

Time: O(9^81) worst | Space: O(1)

---

Q3. Word Search in Grid

Problem: Does the word exist in the 2D grid? Connected cells, no reuse.

---

🧠 How to Approach This

Step 1: DFS from each matching start. Mark visited by replacing char. Restore on backtrack.

function wordSearch(board, word) {
    const rows = board.length;
    const cols = board[0].length;

    function dfs(r, c, idx) {
        if (idx === word.length) return true; // found!

        if (r < 0 || r >= rows || c < 0 || c >= cols ||
            board[r][c] !== word[idx]) return false;

        // CHOOSE: mark visited
        const temp = board[r][c];
        board[r][c] = '#';

        // EXPLORE 4 directions
        const found = dfs(r + 1, c, idx + 1) ||
                      dfs(r - 1, c, idx + 1) ||
                      dfs(r, c + 1, idx + 1) ||
                      dfs(r, c - 1, idx + 1);

        // UN-CHOOSE: restore
        board[r][c] = temp;

        return found;
    }

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
}

const board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']];
console.log(wordSearch(board, 'ABCCED')); // true
console.log(wordSearch(board, 'ABCB'));   // false

Time: O(m×n×4^L) | Space: O(L)

---

Q4. Generate Parentheses

Problem: All valid combinations of n pairs of parentheses.

---

🧠 How to Approach This

Step 1 — Rules:

- Add '(' if openCount < n

- Add ')' if closeCount < openCount

- Base: length == 2n

function generateParentheses(n) {
    const result = [];

    function backtrack(current, open, close) {
        if (current.length === 2 * n) {
            result.push(current);
            return;
        }
        if (open < n)     backtrack(current + '(', open + 1, close);
        if (close < open) backtrack(current + ')', open, close + 1);
    }

    backtrack('', 0, 0);
    return result;
}

console.log(generateParentheses(3));
// ["((()))","(()())","(())()","()(())","()()()"]

Time: O(4ⁿ/√n) | Space: O(n)

---

Q5. Letter Combinations of Phone Number

Problem: All letter combinations for a digit string (T9 keyboard).

---

🧠 How to Approach This

Step 1: Map digit → letters. For each digit's letters: append, recurse next digit, pop.

function letterCombinations(digits) {
    if (!digits) return [];

    const phoneMap = {
        '2':'abc','3':'def','4':'ghi','5':'jkl',
        '6':'mno','7':'pqrs','8':'tuv','9':'wxyz'
    };

    const result = [];

    function backtrack(idx, current) {
        if (idx === digits.length) { result.push(current); return; }

        for (const ch of phoneMap[digits[idx]]) {
            backtrack(idx + 1, current + ch);
        }
    }

    backtrack(0, '');
    return result;
}

console.log(letterCombinations('23'));
// ['ad','ae','af','bd','be','bf','cd','ce','cf']

Time: O(4ⁿ × n) | Space: O(n)

---

Backtracking Summary