📌 Day 19: The Backtracking Pattern (Amazon Interview Series)

Backtracking is a brute-force with pruning technique used to solve constraint satisfaction problems.
Amazon loves this pattern because it tests:

• Recursive problem-solving skills
• Ability to prune search space
• Understanding of constraints

---

🔑 When to Use Backtracking

• You need to generate all possible solutions.
• Problem involves combinatorial search (subsets, permutations, partitions).
• You can prune invalid paths early to save time.

---

📝 Problem 1: Word Search (Amazon Favorite)

👉 Amazon-style phrasing:
Given a 2D grid of letters and a word, check if the word exists in the grid. You can move up, down, left, right, but cannot reuse the same cell.

Java Solution

public class WordSearch {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, i, j, word, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int i, int j, String word, int idx) {
        if (idx == word.length()) return true;
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length 
            || board[i][j] != word.charAt(idx)) return false;

        char temp = board[i][j];
        board[i][j] = '#'; // mark visited
        boolean found = dfs(board, i+1, j, word, idx+1) ||
                        dfs(board, i-1, j, word, idx+1) ||
                        dfs(board, i, j+1, word, idx+1) ||
                        dfs(board, i, j-1, word, idx+1);
        board[i][j] = temp; // backtrack
        return found;
    }

    public static void main(String[] args) {
        WordSearch ws = new WordSearch();
        char[][] board = {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        };
        System.out.println(ws.exist(board, "ABCCED")); // true
    }
}

✅ Key Insight: DFS with backtracking ensures cells are not reused.

---

📝 Problem 2: N-Queens

👉 Amazon-style phrasing:
Place N queens on an N x N chessboard so that no two queens attack each other.

Java Solution

import java.util.*;

public class NQueens {
    List<List<String>> solutions = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(board, 0);
        return solutions;
    }

    private void backtrack(char[][] board, int row) {
        if (row == board.length) {
            List<String> sol = new ArrayList<>();
            for (char[] r : board) sol.add(new String(r));
            solutions.add(sol);
            return;
        }

        for (int col = 0; col < board.length; col++) {
            if (isSafe(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(board, row + 1);
                board[row][col] = '.'; // backtrack
            }
        }
    }

    private boolean isSafe(char[][] board, int row, int col) {
        for (int i = 0; i < row; i++) if (board[i][col] == 'Q') return false;
        for (int i = row-1, j = col-1; i>=0 && j>=0; i--, j--) if (board[i][j] == 'Q') return false;
        for (int i = row-1, j = col+1; i>=0 && j<board.length; i--, j++) if (board[i][j] == 'Q') return false;
        return true;
    }

    public static void main(String[] args) {
        NQueens nq = new NQueens();
        List<List<String>> result = nq.solveNQueens(4);
        System.out.println(result);
    }
}

✅ Key Insight: Use DFS + pruning to explore valid queen placements.

---

📝 Problem 3: Combination Sum

👉 Amazon-style phrasing:
Given an array of candidates and a target, find all unique combinations that sum up to the target.

Java Solution

import java.util.*;

public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> temp, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] <= target) {
                temp.add(candidates[i]);
                backtrack(candidates, target - candidates[i], i, temp, result);
                temp.remove(temp.size() - 1); // backtrack
            }
        }
    }

    public static void main(String[] args) {
        CombinationSum cs = new CombinationSum();
        System.out.println(cs.combinationSum(new int[]{2,3,6,7}, 7)); // [[2,2,3],[7]]
    }
}

✅ Key Insight: Recursively try candidates, backtrack when sum exceeds target.

---

🎯 Amazon Variations of Backtracking Problems

• Generate Parentheses → valid bracket sequences.
• Sudoku Solver → fill grid with constraints.
• Word Break II → segment strings into dictionary words.
• Letter Combinations of Phone Number → keypad mappings.
• Rat in a Maze → pathfinding with obstacles.

---

🏆 Key Takeaways

• Backtracking = DFS + pruning.
• Use when problem requires all solutions or constraint validation.
• Amazon tests this to see if you can balance recursion depth + pruning efficiency.

---

📅 Next in the series (Day 20):
👉 Graph Pattern – BFS, DFS, Topological Sort, and Union-Find (Amazon’s most common advanced pattern).

---