🧠 BACKTRACKING MASTER TEMPLATE

🔧 Core Idea:

Backtracking = DFS + state restore (undo) after recursion.

Recursive structure:

void backtrack(State currentState) {
    if (isGoalState(currentState)) {
        saveResult(currentState);
        return;
    }

    for (Choice choice : getValidChoices(currentState)) {
        apply(choice);           // make a move
        backtrack(newState);     // explore
        undo(choice);            // backtrack
    }
}

---

📦 Generic Java Template

public class BacktrackingTemplate {

    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> backtrackDriver(int[] nums) {
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[nums.length]; // optional for permutations
        backtrack(nums, path, used);
        return result;
    }

    private void backtrack(int[] nums, List<Integer> path, boolean[] used) {
        // Goal condition
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue; // Skip already used

            // Make choice
            path.add(nums[i]);
            used[i] = true;

            // Explore
            backtrack(nums, path, used);

            // Undo choice
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

---

🧭 Pattern-Specific Backtracking Templates

---

1️⃣ Subsets / Power Set (Take or Not Take)

void backtrack(int i, List<Integer> path) {
    result.add(new ArrayList<>(path)); // capture every subset

    for (int j = i; j < nums.length; j++) {
        path.add(nums[j]);       // take
        backtrack(j + 1, path);  // move forward
        path.remove(path.size() - 1); // backtrack
    }
}

---

2️⃣ Combinations (Fixed Size k)

void backtrack(int start, List<Integer> path) {
    if (path.size() == k) {
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = start; i <= n; i++) {
        path.add(i);
        backtrack(i + 1, path); // ensure no repetition
        path.remove(path.size() - 1);
    }
}

---

3️⃣ Permutations (All Arrangements)

void backtrack(List<Integer> path, boolean[] used) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrack(path, used);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

---

4️⃣ N-Queens

void backtrack(int row) {
    if (row == n) {
        result.add(generateBoard());
        return;
    }

    for (int col = 0; col < n; col++) {
        if (isValid(row, col)) {
            placeQueen(row, col);
            backtrack(row + 1);
            removeQueen(row, col);
        }
    }
}

---

5️⃣ Word Search (DFS on Grid)

boolean backtrack(int r, int c, int index) {
    if (index == word.length()) return true;

    if (r < 0 || c < 0 || r >= m || c >= n || board[r][c] != word.charAt(index))
        return false;

    char temp = board[r][c];
    board[r][c] = '#'; // mark as visited

    for (int[] d : directions) {
        if (backtrack(r + d[0], c + d[1], index + 1)) return true;
    }

    board[r][c] = temp; // unmark
    return false;
}

---

6️⃣ Sudoku Solver

boolean backtrack() {
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] == '.') {
                for (char d = '1'; d <= '9'; d++) {
                    if (isValid(board, r, c, d)) {
                        board[r][c] = d;
                        if (backtrack()) return true;
                        board[r][c] = '.';
                    }
                }
                return false;
            }
        }
    }
    return true;
}

---

🧩 Core Design Principles

Principle	Description
Choice	What options do I have at each step?
Constraints	Can I prune illegal choices early?
Goal	When is a complete solution formed?
Backtrack	Undo the choice after recursion.
State Representation	Current path, visited[], board[][], etc.
Pruning	Use early exits, validity checks, deduplication

---

📌 Bonus: Deduplication (for Unique Permutations)

Sort input and skip duplicates:

if (i > start && nums[i] == nums[i - 1]) continue; // Skip duplicates

---