[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":90,"_73":91,"_35":92},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",47,"title","Backtracking","slug","algorithms-part-20-backtracking","excerpt","Master the backtracking template for systematic search with pruning. Solve N-Queens, Sudoku, permutation problems, and use branch and bound for optimization.","# Part 20: Backtracking & Branch and Bound - Systematic Search with Pruning\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| Time to Read | 35 minutes |\n| Prerequisites | Part 2 (Recursion), Part 16 (DP basics) |\n| Key Concepts | Backtracking Template, Pruning, N-Queens, Sudoku, Branch & Bound |\n| Difficulty | ⭐⭐⭐ (Intermediate) |\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ BACKTRACKING │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ EXPLORE → CHOOSE → EXPLORE → BACKTRACK │\n│ │\n│ ○ root │\n│ / | \\ │\n│ ○ ○ ○ Level 1: choices │\n│ /| | |\\ │\n│ ○ ○ × ○ ○ Level 2: × = pruned (invalid) │\n│ /| | |\\ │\n│ ○ × ○ × ○ Level 3: leaves = solutions │\n│ │\n│ Key insight: Don't explore paths that can't lead to solution │\n│ │\n│ Template: │\n│ ┌─────────────────────────────────────────────────────────┐ │\n│ │ backtrack(state): │ │\n│ │ if isComplete(state): │ │\n│ │ addToResults(state) │ │\n│ │ return │ │\n│ │ │ │\n│ │ for choice in getChoices(state): │ │\n│ │ if isValid(choice): │ │\n│ │ makeChoice(choice) │ │\n│ │ backtrack(state) │ │\n│ │ undoChoice(choice) ← KEY STEP │ │\n│ └─────────────────────────────────────────────────────────┘ │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🎯 What You'll Learn\n\nAfter completing this article, you will be able to:\n\n1. **Apply the backtracking template**: Systematic approach for any problem\n2. **Solve classic problems**: N-Queens, Sudoku, permutations\n3. **Prune effectively**: Cut search space dramatically\n4. **Use branch and bound**: Optimization with bounds\n5. **Choose between approaches**: Backtracking vs DP vs brute force\n\n---\n\n## 🔥 Production Story: The Configuration Solver\n\nA network equipment company needed to find valid configurations for complex hardware setups with many constraints.\n\n### The Problem\n\n```java\n// ❌ Brute force: Try all combinations\npublic class NaiveConfigSolver {\n public List findValidConfigs(Hardware hardware) {\n List valid = new ArrayList<>();\n\n // 50 settings, each with 10 options = 10^50 combinations\n // IMPOSSIBLE to check all\n for (Configuration config : allConfigurations()) {\n if (isValid(config)) {\n valid.add(config);\n }\n }\n return valid;\n }\n}\n```\n\n### The Solution: Backtracking with Constraint Propagation\n\n```java\n// ✅ Backtracking with pruning\npublic class ConfigSolver {\n private Hardware hardware;\n private List solutions;\n\n public List findValidConfigs(Hardware hardware) {\n this.hardware = hardware;\n this.solutions = new ArrayList<>();\n\n Configuration partial = new Configuration();\n backtrack(partial, 0);\n\n return solutions;\n }\n\n private void backtrack(Configuration config, int settingIndex) {\n // Pruning: check constraints incrementally\n if (!satisfiesConstraintsSoFar(config)) {\n return; // Prune this branch\n }\n\n // Complete configuration found\n if (settingIndex == hardware.getSettingsCount()) {\n solutions.add(config.copy());\n return;\n }\n\n Setting setting = hardware.getSetting(settingIndex);\n\n // Try each option for this setting\n for (Option option : setting.getOptions()) {\n config.set(settingIndex, option);\n backtrack(config, settingIndex + 1);\n config.unset(settingIndex); // Backtrack\n }\n }\n\n private boolean satisfiesConstraintsSoFar(Configuration config) {\n // Check only constraints involving set settings\n // Early termination if any constraint violated\n for (Constraint c : hardware.getConstraints()) {\n if (c.canEvaluate(config) && !c.isSatisfied(config)) {\n return false;\n }\n }\n return true;\n }\n}\n```\n\n### The Impact\n\n| Metric | Brute Force | Backtracking |\n|--------|-------------|--------------|\n| Search space | 10^50 | ~10^6 (pruned) |\n| Time for solution | Impossible | 0.3 seconds |\n| Memory | N/A | O(depth) |\n| Valid configs found | 0 | 847 |\n\n---\n\n## 🧠 Mental Model: The Maze Explorer\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ BACKTRACKING AS MAZE EXPLORATION │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ ┌───┬───┬───┬───┬───┐ │\n│ │ S │ │ │ █ │ │ S = Start │\n│ ├───┼───┼───┼───┼───┤ E = End (goal) │\n│ │ │ █ │ │ │ │ █ = Wall (invalid) │\n│ ├───┼───┼───┼───┼───┤ · = Path tried │\n│ │ │ │ █ │ │ │ ○ = Current position │\n│ ├───┼───┼───┼───┼───┤ │\n│ │ █ │ │ │ █ │ │ │\n│ ├───┼───┼───┼───┼───┤ │\n│ │ │ │ │ │ E │ │\n│ └───┴───┴───┴───┴───┘ │\n│ │\n│ Algorithm: │\n│ 1. From current position, try each direction │\n│ 2. If direction leads to wall or visited → skip (prune) │\n│ 3. Move to new position, mark as visited │\n│ 4. If at goal → found solution! │\n│ 5. If stuck → go back (backtrack), try next direction │\n│ │\n│ Key: Marking visited prevents infinite loops │\n│ Backtracking undoes the \"visited\" mark │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🔬 Deep Dive: The Backtracking Template\n\n### General Template\n\n```java\npublic class BacktrackingTemplate {\n\n public List solve(Problem problem) {\n List solutions = new ArrayList<>();\n State initialState = new State();\n backtrack(problem, initialState, solutions);\n return solutions;\n }\n\n private void backtrack(Problem problem, State state, List solutions) {\n // 1. Check if current state is a complete solution\n if (isComplete(state)) {\n solutions.add(state.toSolution());\n return; // Or continue if finding all solutions\n }\n\n // 2. Get possible choices at current state\n for (Choice choice : getChoices(problem, state)) {\n\n // 3. Pruning: Skip invalid choices early\n if (!isValid(state, choice)) {\n continue;\n }\n\n // 4. Make the choice\n state.apply(choice);\n\n // 5. Recurse\n backtrack(problem, state, solutions);\n\n // 6. Undo the choice (backtrack)\n state.undo(choice);\n }\n }\n}\n```\n\n### Subsets (Power Set)\n\n```java\npublic class Subsets {\n public List> subsets(int[] nums) {\n List> result = new ArrayList<>();\n backtrack(nums, 0, new ArrayList<>(), result);\n return result;\n }\n\n private void backtrack(int[] nums, int start,\n List current, List> result) {\n // Every state is a valid subset\n result.add(new ArrayList<>(current));\n\n // Try adding each remaining element\n for (int i = start; i < nums.length; i++) {\n current.add(nums[i]); // Choose\n backtrack(nums, i + 1, current, result); // Explore\n current.remove(current.size() - 1); // Un-choose\n }\n }\n}\n```\n\n### Permutations\n\n```java\npublic class Permutations {\n public List> permute(int[] nums) {\n List> result = new ArrayList<>();\n boolean[] used = new boolean[nums.length];\n backtrack(nums, used, new ArrayList<>(), result);\n return result;\n }\n\n private void backtrack(int[] nums, boolean[] used,\n List current, List> result) {\n // Complete permutation\n if (current.size() == nums.length) {\n result.add(new ArrayList<>(current));\n return;\n }\n\n for (int i = 0; i < nums.length; i++) {\n if (used[i]) continue; // Skip used elements\n\n used[i] = true;\n current.add(nums[i]);\n\n backtrack(nums, used, current, result);\n\n current.remove(current.size() - 1);\n used[i] = false;\n }\n }\n\n // Permutations with duplicates\n public List> permuteUnique(int[] nums) {\n Arrays.sort(nums); // Sort to handle duplicates\n List> result = new ArrayList<>();\n boolean[] used = new boolean[nums.length];\n backtrack2(nums, used, new ArrayList<>(), result);\n return result;\n }\n\n private void backtrack2(int[] nums, boolean[] used,\n List current, List> result) {\n if (current.size() == nums.length) {\n result.add(new ArrayList<>(current));\n return;\n }\n\n for (int i = 0; i < nums.length; i++) {\n if (used[i]) continue;\n\n // Skip duplicates: if same as previous and previous not used\n if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;\n\n used[i] = true;\n current.add(nums[i]);\n backtrack2(nums, used, current, result);\n current.remove(current.size() - 1);\n used[i] = false;\n }\n }\n}\n```\n\n### Combinations\n\n```java\npublic class Combinations {\n // Choose k elements from n\n public List> combine(int n, int k) {\n List> result = new ArrayList<>();\n backtrack(n, k, 1, new ArrayList<>(), result);\n return result;\n }\n\n private void backtrack(int n, int k, int start,\n List current, List> result) {\n if (current.size() == k) {\n result.add(new ArrayList<>(current));\n return;\n }\n\n // Pruning: need k - current.size() more elements\n // Can't get enough from [start, n] if n - start + 1 < k - current.size()\n int need = k - current.size();\n for (int i = start; i <= n - need + 1; i++) {\n current.add(i);\n backtrack(n, k, i + 1, current, result);\n current.remove(current.size() - 1);\n }\n }\n\n // Combination Sum: find combinations that sum to target\n public List> combinationSum(int[] candidates, int target) {\n List> result = new ArrayList<>();\n Arrays.sort(candidates);\n backtrackSum(candidates, target, 0, new ArrayList<>(), result);\n return result;\n }\n\n private void backtrackSum(int[] candidates, int remaining, int start,\n List current, List> result) {\n if (remaining == 0) {\n result.add(new ArrayList<>(current));\n return;\n }\n\n for (int i = start; i < candidates.length; i++) {\n // Pruning: if current candidate > remaining, all after are too big\n if (candidates[i] > remaining) break;\n\n current.add(candidates[i]);\n // Same element can be used again, so pass i not i+1\n backtrackSum(candidates, remaining - candidates[i], i, current, result);\n current.remove(current.size() - 1);\n }\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: N-Queens Problem\n\n### The Problem\n\nPlace N queens on an N×N chessboard so no two attack each other.\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ N-QUEENS (N=4) │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Solution 1: Solution 2: │\n│ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ │\n│ │ │ Q │ │ │ │ │ │ Q │ │ │\n│ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤ │\n│ │ │ │ │ Q │ │ Q │ │ │ │ │\n│ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤ │\n│ │ Q │ │ │ │ │ │ │ │ Q │ │\n│ ├───┼───┼───┼───┤ ├───┼───┼───┼───┤ │\n│ │ │ │ Q │ │ │ │ Q │ │ │ │\n│ └───┴───┴───┴───┘ └───┴───┴───┴───┘ │\n│ │\n│ Constraint: No two queens share row, column, or diagonal │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Implementation\n\n```java\npublic class NQueens {\n public List> solveNQueens(int n) {\n List> solutions = new ArrayList<>();\n int[] queens = new int[n]; // queens[row] = column of queen in that row\n Arrays.fill(queens, -1);\n\n // Track which columns and diagonals are attacked\n boolean[] cols = new boolean[n];\n boolean[] diag1 = new boolean[2 * n - 1]; // row - col + n - 1\n boolean[] diag2 = new boolean[2 * n - 1]; // row + col\n\n backtrack(n, 0, queens, cols, diag1, diag2, solutions);\n return solutions;\n }\n\n private void backtrack(int n, int row, int[] queens,\n boolean[] cols, boolean[] diag1, boolean[] diag2,\n List> solutions) {\n if (row == n) {\n solutions.add(buildBoard(queens, n));\n return;\n }\n\n for (int col = 0; col < n; col++) {\n int d1 = row - col + n - 1;\n int d2 = row + col;\n\n // Pruning: skip if column or diagonal is attacked\n if (cols[col] || diag1[d1] || diag2[d2]) {\n continue;\n }\n\n // Place queen\n queens[row] = col;\n cols[col] = true;\n diag1[d1] = true;\n diag2[d2] = true;\n\n backtrack(n, row + 1, queens, cols, diag1, diag2, solutions);\n\n // Remove queen (backtrack)\n queens[row] = -1;\n cols[col] = false;\n diag1[d1] = false;\n diag2[d2] = false;\n }\n }\n\n private List buildBoard(int[] queens, int n) {\n List board = new ArrayList<>();\n for (int row = 0; row < n; row++) {\n char[] rowChars = new char[n];\n Arrays.fill(rowChars, '.');\n rowChars[queens[row]] = 'Q';\n board.add(new String(rowChars));\n }\n return board;\n }\n\n // Count solutions only (faster)\n public int totalNQueens(int n) {\n return countSolutions(n, 0, 0, 0, 0);\n }\n\n // Using bitmasks for faster checking\n private int countSolutions(int n, int row, int cols, int diag1, int diag2) {\n if (row == n) return 1;\n\n int count = 0;\n int available = ((1 << n) - 1) & ~(cols | diag1 | diag2);\n\n while (available != 0) {\n int pos = available & (-available); // Lowest set bit\n available ^= pos; // Remove this position\n\n count += countSolutions(n, row + 1,\n cols | pos,\n (diag1 | pos) << 1,\n (diag2 | pos) >> 1);\n }\n\n return count;\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Sudoku Solver\n\n### Implementation\n\n```java\npublic class SudokuSolver {\n public void solveSudoku(char[][] board) {\n solve(board);\n }\n\n private boolean solve(char[][] board) {\n // Find empty cell\n for (int row = 0; row < 9; row++) {\n for (int col = 0; col < 9; col++) {\n if (board[row][col] == '.') {\n // Try each digit\n for (char c = '1'; c <= '9'; c++) {\n if (isValid(board, row, col, c)) {\n board[row][col] = c;\n\n if (solve(board)) {\n return true;\n }\n\n board[row][col] = '.'; // Backtrack\n }\n }\n return false; // No valid digit found\n }\n }\n }\n return true; // All cells filled\n }\n\n private boolean isValid(char[][] board, int row, int col, char c) {\n // Check row\n for (int j = 0; j < 9; j++) {\n if (board[row][j] == c) return false;\n }\n\n // Check column\n for (int i = 0; i < 9; i++) {\n if (board[i][col] == c) return false;\n }\n\n // Check 3x3 box\n int boxRow = (row / 3) * 3;\n int boxCol = (col / 3) * 3;\n for (int i = 0; i < 3; i++) {\n for (int j = 0; j < 3; j++) {\n if (board[boxRow + i][boxCol + j] == c) return false;\n }\n }\n\n return true;\n }\n\n // Optimized with bitmasks\n public void solveSudokuOptimized(char[][] board) {\n int[] rows = new int[9]; // Bitmask for each row\n int[] cols = new int[9]; // Bitmask for each column\n int[][] boxes = new int[3][3]; // Bitmask for each 3x3 box\n\n // Initialize constraints\n for (int i = 0; i < 9; i++) {\n for (int j = 0; j < 9; j++) {\n if (board[i][j] != '.') {\n int num = board[i][j] - '1';\n int mask = 1 << num;\n rows[i] |= mask;\n cols[j] |= mask;\n boxes[i/3][j/3] |= mask;\n }\n }\n }\n\n solveOptimized(board, 0, rows, cols, boxes);\n }\n\n private boolean solveOptimized(char[][] board, int cell,\n int[] rows, int[] cols, int[][] boxes) {\n if (cell == 81) return true;\n\n int row = cell / 9;\n int col = cell % 9;\n\n if (board[row][col] != '.') {\n return solveOptimized(board, cell + 1, rows, cols, boxes);\n }\n\n int used = rows[row] | cols[col] | boxes[row/3][col/3];\n\n for (int num = 0; num < 9; num++) {\n int mask = 1 << num;\n if ((used & mask) == 0) {\n board[row][col] = (char) ('1' + num);\n rows[row] |= mask;\n cols[col] |= mask;\n boxes[row/3][col/3] |= mask;\n\n if (solveOptimized(board, cell + 1, rows, cols, boxes)) {\n return true;\n }\n\n board[row][col] = '.';\n rows[row] ^= mask;\n cols[col] ^= mask;\n boxes[row/3][col/3] ^= mask;\n }\n }\n\n return false;\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Branch and Bound\n\n### The Concept\n\nBranch and Bound adds bounding functions to prune branches that can't improve on the best solution found so far.\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ BRANCH AND BOUND │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Standard Backtracking: │\n│ - Prunes invalid solutions │\n│ │\n│ Branch and Bound (for optimization): │\n│ - Also prunes solutions that can't beat current best │\n│ │\n│ Components: │\n│ 1. Branch: Split problem into subproblems │\n│ 2. Bound: Calculate optimistic estimate for subtree │\n│ 3. Prune: If bound ≤ best found, skip this branch │\n│ │\n│ Example for minimization: │\n│ │\n│ Current best = 50 │\n│ ○ │\n│ / | \\ │\n│ ○ ○ ○ │\n│ lb=30 lb=55 lb=40 │\n│ ↓ ✗ ↓ lb=55 > 50, prune! │\n│ explore explore │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### TSP with Branch and Bound\n\n```java\npublic class TSPBranchAndBound {\n private int n;\n private int[][] dist;\n private int bestCost;\n private int[] bestPath;\n\n public int[] solve(int[][] distances) {\n this.n = distances.length;\n this.dist = distances;\n this.bestCost = Integer.MAX_VALUE;\n this.bestPath = new int[n];\n\n int[] path = new int[n];\n boolean[] visited = new boolean[n];\n\n path[0] = 0;\n visited[0] = true;\n\n branchAndBound(path, visited, 1, 0);\n\n return bestPath;\n }\n\n private void branchAndBound(int[] path, boolean[] visited,\n int level, int currentCost) {\n if (level == n) {\n // Complete tour: add return to start\n int totalCost = currentCost + dist[path[n-1]][0];\n if (totalCost < bestCost) {\n bestCost = totalCost;\n System.arraycopy(path, 0, bestPath, 0, n);\n }\n return;\n }\n\n for (int i = 0; i < n; i++) {\n if (!visited[i]) {\n int newCost = currentCost + dist[path[level-1]][i];\n\n // Bound: optimistic estimate of remaining cost\n int lowerBound = newCost + calculateLowerBound(visited, i);\n\n // Prune if bound >= best\n if (lowerBound < bestCost) {\n path[level] = i;\n visited[i] = true;\n\n branchAndBound(path, visited, level + 1, newCost);\n\n visited[i] = false;\n }\n }\n }\n }\n\n // Simple lower bound: sum of minimum outgoing edges\n private int calculateLowerBound(boolean[] visited, int current) {\n int bound = 0;\n\n // Minimum edge from current to unvisited\n int minFromCurrent = Integer.MAX_VALUE;\n for (int i = 0; i < n; i++) {\n if (!visited[i] && i != current) {\n minFromCurrent = Math.min(minFromCurrent, dist[current][i]);\n }\n }\n if (minFromCurrent != Integer.MAX_VALUE) bound += minFromCurrent;\n\n // Minimum edge from each unvisited to anywhere\n for (int i = 0; i < n; i++) {\n if (!visited[i] && i != current) {\n int minFrom = dist[i][0]; // Can return to start\n for (int j = 0; j < n; j++) {\n if (j != i && (!visited[j] || j == 0)) {\n minFrom = Math.min(minFrom, dist[i][j]);\n }\n }\n bound += minFrom;\n }\n }\n\n return bound;\n }\n}\n```\n\n### 0/1 Knapsack with Branch and Bound\n\n```java\npublic class KnapsackBranchAndBound {\n private int n;\n private int[] weights, values;\n private int capacity;\n private int maxValue;\n\n public int solve(int[] weights, int[] values, int capacity) {\n this.n = weights.length;\n this.weights = weights;\n this.values = values;\n this.capacity = capacity;\n this.maxValue = 0;\n\n // Sort by value/weight ratio (for better bound)\n Integer[] indices = new Integer[n];\n for (int i = 0; i < n; i++) indices[i] = i;\n Arrays.sort(indices, (a, b) ->\n Double.compare((double) values[b] / weights[b],\n (double) values[a] / weights[a]));\n\n branchAndBound(indices, 0, 0, 0);\n return maxValue;\n }\n\n private void branchAndBound(Integer[] indices, int level,\n int currentWeight, int currentValue) {\n if (level == n) {\n maxValue = Math.max(maxValue, currentValue);\n return;\n }\n\n int idx = indices[level];\n\n // Upper bound using fractional relaxation\n double bound = currentValue + fractionalBound(indices, level, currentWeight);\n\n // Prune if bound <= maxValue (maximization)\n if (bound <= maxValue) {\n return;\n }\n\n // Branch 1: Take item (if fits)\n if (currentWeight + weights[idx] <= capacity) {\n branchAndBound(indices, level + 1,\n currentWeight + weights[idx],\n currentValue + values[idx]);\n }\n\n // Branch 2: Don't take item\n branchAndBound(indices, level + 1, currentWeight, currentValue);\n }\n\n private double fractionalBound(Integer[] indices, int level, int weight) {\n double bound = 0;\n int remainingCapacity = capacity - weight;\n\n for (int i = level; i < n && remainingCapacity > 0; i++) {\n int idx = indices[i];\n if (weights[idx] <= remainingCapacity) {\n bound += values[idx];\n remainingCapacity -= weights[idx];\n } else {\n bound += (double) values[idx] * remainingCapacity / weights[idx];\n break;\n }\n }\n\n return bound;\n }\n}\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Forgetting to Undo Choice\n\n```java\n// ❌ WRONG: Not backtracking\nvoid backtrack(State state) {\n for (Choice c : choices) {\n state.apply(c);\n backtrack(state);\n // Missing: state.undo(c);\n }\n}\n\n// ✅ CORRECT: Always undo\nvoid backtrack(State state) {\n for (Choice c : choices) {\n state.apply(c);\n backtrack(state);\n state.undo(c); // Backtrack!\n }\n}\n```\n\n---\n\n### Mistake 2: Modifying Loop Variable\n\n```java\n// ❌ WRONG: Modifying list while iterating\nvoid backtrack(List current) {\n for (int i = 0; i < nums.length; i++) {\n current.add(nums[i]);\n backtrack(current);\n // current.remove(nums[i]); // WRONG: removes by value, not index\n }\n}\n\n// ✅ CORRECT: Remove by index\nvoid backtrack(List current) {\n for (int i = 0; i < nums.length; i++) {\n current.add(nums[i]);\n backtrack(current);\n current.remove(current.size() - 1); // Remove last element\n }\n}\n```\n\n---\n\n### Mistake 3: Adding Reference Instead of Copy\n\n```java\n// ❌ WRONG: Adding reference\nvoid backtrack(List current, List> result) {\n if (isComplete(current)) {\n result.add(current); // Same list modified later!\n return;\n }\n // ...\n}\n\n// ✅ CORRECT: Add copy\nvoid backtrack(List current, List> result) {\n if (isComplete(current)) {\n result.add(new ArrayList<>(current)); // Copy!\n return;\n }\n // ...\n}\n```\n\n---\n\n## 🐛 Debug This: Permutation Bug\n\nThis permutation generator has a bug. Can you find it?\n\n```java\npublic List> permute(int[] nums) {\n List> result = new ArrayList<>();\n backtrack(nums, new ArrayList<>(), result);\n return result;\n}\n\nvoid backtrack(int[] nums, List current, List> result) {\n if (current.size() == nums.length) {\n result.add(new ArrayList<>(current));\n return;\n }\n\n for (int i = 0; i < nums.length; i++) {\n // BUG IS HERE\n if (current.contains(nums[i])) continue;\n\n current.add(nums[i]);\n backtrack(nums, current, result);\n current.remove(current.size() - 1);\n }\n}\n```\n\n

🔍 Click to reveal the bug

\n\n**Bug**: Using `contains(nums[i])` to check if element is used. This fails when array has duplicates!\n\n```java\n// ❌ BUG: contains() checks by value, not by index\nif (current.contains(nums[i])) continue;\n\n// ✅ FIX: Use boolean array to track indices\nboolean[] used = new boolean[nums.length];\n\nvoid backtrack(int[] nums, boolean[] used, List current, ...) {\n if (current.size() == nums.length) {\n result.add(new ArrayList<>(current));\n return;\n }\n\n for (int i = 0; i < nums.length; i++) {\n if (used[i]) continue; // Check index, not value\n\n used[i] = true;\n current.add(nums[i]);\n backtrack(nums, used, current, result);\n current.remove(current.size() - 1);\n used[i] = false;\n }\n}\n```\n\n**Example where bug manifests**:\n```\nnums = [1, 1, 2]\nBug: \"1 is already in current\" - skips valid permutations\nResult: Missing [1,1,2], [1,2,1], [2,1,1]\n```\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Generate Parentheses ⭐⭐\n\nGenerate all valid combinations of n pairs of parentheses.\n\n```java\npublic List generateParenthesis(int n) {\n // Track open and close counts\n}\n```\n\n---\n\n### Exercise 2: Letter Combinations of Phone ⭐⭐\n\nGiven digits 2-9, return all letter combinations (like phone keypad).\n\n```java\npublic List letterCombinations(String digits) {\n // Map digit to letters, backtrack\n}\n```\n\n---\n\n### Exercise 3: Word Search ⭐⭐⭐\n\nFind if word exists in 2D grid (adjacent cells, no reuse).\n\n```java\npublic boolean exist(char[][] board, String word) {\n // Backtrack from each cell\n}\n```\n\n---\n\n### Exercise 4: Palindrome Partitioning ⭐⭐⭐\n\nPartition string so every substring is a palindrome.\n\n```java\npublic List> partition(String s) {\n // Backtrack with isPalindrome check\n}\n```\n\n---\n\n### Exercise 5: Expression Add Operators ⭐⭐⭐⭐\n\nAdd +, -, * between digits to reach target.\n\n```java\npublic List addOperators(String num, int target) {\n // Track current value and last operand (for * precedence)\n}\n```\n\n---\n\n## 🎤 Interview Questions\n\n### Q1: \"What's the difference between backtracking and DFS?\"\n\n**Answer**:\n\nDFS is a traversal technique. Backtracking uses DFS but with:\n1. **State modification**: Change state before recursing\n2. **State restoration**: Undo changes after recursing\n3. **Pruning**: Skip invalid branches early\n\n```java\n// Pure DFS: just traverse\nvoid dfs(Node node) {\n visit(node);\n for (Node child : node.children) {\n dfs(child);\n }\n}\n\n// Backtracking: modify, recurse, restore\nvoid backtrack(State state) {\n if (isComplete(state)) { record(); return; }\n\n for (Choice c : choices) {\n if (isValid(c)) {\n state.apply(c); // Modify\n backtrack(state);\n state.undo(c); // Restore\n }\n }\n}\n```\n\n---\n\n### Q2: \"How do you optimize backtracking?\"\n\n**Answer**:\n\n1. **Pruning**: Skip invalid branches early\n ```java\n if (!canLeadToSolution(state)) return;\n ```\n\n2. **Ordering**: Try most constrained choice first\n ```java\n // Sudoku: fill cell with fewest possibilities first\n ```\n\n3. **Constraint propagation**: Reduce choices after each decision\n ```java\n // After placing queen, mark attacked positions\n ```\n\n4. **Symmetry breaking**: Avoid equivalent solutions\n ```java\n // N-Queens: first queen only in left half of first row\n ```\n\n5. **Memoization**: Cache repeated subproblems\n ```java\n if (memo.contains(state)) return memo.get(state);\n ```\n\n---\n\n### Q3: \"When should I use backtracking vs DP?\"\n\n**Answer**:\n\n| Backtracking | DP |\n|--------------|---|\n| Find all solutions | Find optimal/count |\n| Solutions have structure (permutation, subset) | Overlapping subproblems |\n| Constraints are complex | State can be compactly represented |\n| O(b^d) where b=branching, d=depth | Polynomial if states are polynomial |\n\n**Rule of thumb**:\n- Need all solutions → Backtracking\n- Need count/optimal → Try DP first\n- Can't define subproblems → Backtracking\n\n---\n\n### Q4: \"Explain the N-Queens problem and optimize it.\"\n\n**Answer**:\n\n```java\n// Basic: O(N!) time, check all placements\n// Optimized with column/diagonal tracking: O(N!) but better constants\n\n// Key optimizations:\n// 1. One queen per row (implicit in recursion)\n// 2. Track attacked columns with boolean array\n// 3. Track attacked diagonals with boolean arrays\n// - Diagonal 1: row - col + N - 1 (constant along /)\n// - Diagonal 2: row + col (constant along \\)\n\n// 4. Bitmask version for counting:\nint solve(int n, int row, int cols, int d1, int d2) {\n if (row == n) return 1;\n\n int available = ((1 << n) - 1) & ~(cols | d1 | d2);\n int count = 0;\n\n while (available != 0) {\n int pos = available & -available; // Lowest bit\n available ^= pos;\n count += solve(n, row + 1,\n cols | pos,\n (d1 | pos) << 1,\n (d2 | pos) >> 1);\n }\n return count;\n}\n```\n\n---\n\n### Q5: \"How does branch and bound improve over basic backtracking?\"\n\n**Answer**:\n\nBranch and bound adds **bounding functions** for optimization problems:\n\n```\nBacktracking: Prune if state is INVALID\nBranch & Bound: Prune if state CAN'T IMPROVE on best found\n\nFor minimization:\n- Calculate lower bound on solutions in this subtree\n- If lower_bound >= best_found, prune entire subtree\n\nFor maximization:\n- Calculate upper bound\n- If upper_bound <= best_found, prune\n\nExample (TSP):\n- Current path cost: 50\n- Lower bound for remaining: 30 (sum of minimum edges)\n- Total lower bound: 80\n- Best complete tour found: 75\n- 80 > 75 → prune this branch!\n```\n\n---\n\n## 📋 Quick Reference\n\n### Problem Types\n\n| Problem | Key Insight |\n|---------|-------------|\n| Subsets | Include/exclude each element |\n| Permutations | Track used elements |\n| Combinations | Use start index to avoid duplicates |\n| N-Queens | Column + 2 diagonal checks |\n| Sudoku | Row + column + box constraints |\n\n### Complexity\n\n| Problem | Time | Space |\n|---------|------|-------|\n| Subsets | O(2^n) | O(n) |\n| Permutations | O(n!) | O(n) |\n| Combinations(n,k) | O(C(n,k)) | O(k) |\n| N-Queens | O(n!) | O(n) |\n| Sudoku | O(9^(empty cells)) | O(1) |\n\n### Template Summary\n\n```java\nvoid backtrack(State state) {\n if (isComplete(state)) {\n results.add(copy(state));\n return;\n }\n\n for (Choice c : getChoices(state)) {\n if (isValid(c)) {\n apply(c);\n backtrack(state);\n undo(c);\n }\n }\n}\n```\n\n---\n\n## 🔗 What's Next?\n\nIn **Part 21: Probabilistic & Approximation Algorithms**, we'll explore:\n- Randomized algorithms\n- Bloom filters\n- HyperLogLog\n- Approximation algorithms\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| 0 | Full read + subsets/permutations | 90 min |\n| 1 | Quick Reference | 10 min |\n| 3 | N-Queens implementation | 25 min |\n| 7 | Sudoku solver | 30 min |\n| 14 | Debug exercise + B&B | 20 min |\n| 30 | Interview questions | 15 min |\n\n---\n\n**Next**: [Part 21: Probabilistic & Approximation Algorithms →](./algorithms-part-21-probabilistic-algorithms.md)\n\n**Series**: [Algorithms Compendium Index](./algorithms-part-0-series-overview.md)\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.309907Z","createdAt","2026-06-10T07:19:25.310701Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",19,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",20,"author",{"_31":55,"_102":57,"_103":104,"_105":106,"_107":-5,"_108":-5,"_109":-5,"_110":-5,"_111":-5},"category",{"_31":98,"_73":59,"_35":99,"_76":100,"_101":-5},"tags",[79,80,81,82,83],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Algorithms Compendium: From Theory to Production","algorithms-compendium","description","A comprehensive 23-part series covering all essential algorithms for Java developers. From foundational concepts like complexity analysis and recursion, through sorting (QuickSort, MergeSort, TimSort), searching (binary search, string matching), graph algorithms (DFS, BFS, Dijkstra, MST), dynamic programming, greedy algorithms, backtracking, to probabilistic data structures (Bloom filters, HyperLogLog) and interview patterns. Includes real production stories, mental models, exercises, and 100+ interview questions.","isActive",{"_31":96,"_73":34,"_35":97},{"_31":93,"_73":94,"_35":95},{"_31":90,"_73":91,"_35":92},{"_31":87,"_73":88,"_35":89},{"_31":84,"_73":85,"_35":86},203,"Sudoku","sudoku",204,"Pruning","pruning",202,"N-queens","n-queens",201,"Branch And Bound","branch-and-bound",200,"backtracking",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]