6 N皇后问题（放置问题）
决策树的每一层表示棋盘的每一行，每个节点可以做的选择是在该行任意位置放置一个皇后。
路径：board，其中小于row的那些行都已经选好了放皇后的位置
选择列表：第row行的每一个位置
返回条件：row超出borad范围
class Solution { private List<List<String>> res = new ArrayList<>(); public List<List<String>> solveNQueens(int n) { List<String> board = new ArrayList<>(); for(int i = 0; i < n; i ++){ String temp = ""; for(int j = 0; j < n ; j ++){ temp += '.'; } board.add(temp); } backtrack(board, 0); return res; } // 路径：board，其中小于row的那些行都已经选好了放皇后的位置 // 选择列表：第row行的每一个位置 // 返回条件：row超出borad范围 private void backtrack(List<String> board, int row){ if(row == board.size()){ res.add(new ArrayList<>(board)); return; } int n = board.get(row).length(); for(int col = 0; col < n; col ++){ if(!valid(board, row, col)){ continue; } char[] str = board.get(row).toCharArray(); // 做选择 str[col] = 'Q'; board.set(row, new String(str)); // 回溯 backtrack(board, row + 1); // 撤销选择 str[col] = '.'; board.set(row, new String(str)); } } // 是否可以在该位置放置 private boolean valid(List<String> board, int row, int col){ int n = board.get(row).length(); // 检查列 for(int i = 0; i < n; i ++){ if(board.get(i).charAt(col) == 'Q'){ return false; } } // 检查右上方 for(int i = row - 1, j = col + 1; i >= 0 && j < n; i --, j ++){ if(board.get(i).charAt(j) == 'Q'){ return false; } } // 检查左上方 for(int i = row - 1, j = col - 1; i >=0 && j >= 0; i --, j --){ if(board.get(i).charAt(j) == 'Q'){ return false; } } return true; } }
7 搜索所有可行解
7.1 leetcode 39 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
定义递归函数 backtrack(int[] candidates, int target, List<Integer> path, int startIndex) 表示当前在 candidates 数组的第 startIndex 位，还剩 target 要组合，已经组合的列表为 path。
递归的终止条件为 target <= 0 或者 candidates 数组被全部用完。那么在当前的函数中，每次我们可以选择跳过不用第 startIndex 个数，即执行 backtrack(candidates, target, path, startIndex + 1)。也可以选择使用第 startIndex个数，即执行 dfs(candidates, target - candidates[startIndex ], combine, startIndex ).
注意到每个数字可以被无限制重复选取，因此搜索的下标仍为 startIndex 。
class Solution { List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> combinationSum(int[] candidates, int target) { List<Integer> path = new ArrayList<>(); backtrack(candidates, target, path, 0); return result; } private void backtrack(int[] candidates, int target, List<Integer> path, int startIndex){ if(startIndex == candidates.length){ return; } if(target == 0){ result.add(new ArrayList<Integer>(path)); return; } // 不选当前数字 backtrack(candidates, target, path, startIndex + 1); // 选当前数字 if(target >= candidates[startIndex]){ path.add(candidates[startIndex]); // 每个数字可以被无限制重复选取，因此搜索的下标仍为 startIndex backtrack(candidates, target - candidates[startIndex], path, startIndex); // 回溯 path.remove(path.size() - 1); } } }
7.2 组合总和II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
和上面的题目框架是类似的，只不过上题要求数字可以无限次使用，本题要求数字只能被用一次，所以需要去重操作，一个简单的去重思路是将数组进行从小到大排序，当后面一个数字等于前面一个数字时直接continue。其余框架不变。
class Solution { List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<Integer> path = new ArrayList<>(); Arrays.sort(candidates); backtrack(candidates, target, path, 0); return result; } private void backtrack(int[] candidates, int target, List<Integer> path, int startIndex){ if(target == 0){ result.add(new ArrayList<Integer>(path)); return; } for(int i = startIndex; i < candidates.length; i ++){ if(candidates[i] > target){ break; } // 保证不重复 if(i > startIndex && candidates[i] == candidates[i-1]){ continue; } path.add(candidates[i]); backtrack(candidates, target - candidates[i], path, i + 1); path.remove(path.size() - 1); } } }
8 回溯和图的遍历结合
leetcode 79 单次搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
设函数check(i,j,k) 判断以网格的 (i, j) 位置出发，能否搜索到单词 word[k..]
路径：当前匹配到的位置k
返回条件：k移动到word尾或者i，j超出二维数组边界
class Solution { public boolean exist(char[][] board, String word) { for (int i = 0; i < board.length; ++i) { for (int j = 0; j < board[i].length; ++j) { if (board[i][j] == word.charAt(0)) { if (backtrack(board, word, i, j, 0)) return true; } } } return false; } private boolean backtrack(char[][] board, String word, int i, int j, int k){ if (k == word.length()) { return true; } if (i < 0 || j < 0 || i >= board.length || j >= board[i].length) { return false; } if (word.charAt(k) != board[i][j]) { return false; } // 匹配当前位置 char t = board[i][j]; board[i][j] = '0'; boolean res = backtrack(board, word, i + 1, j, k + 1) || backtrack(board, word, i - 1, j, k + 1) || backtrack(board, word, i, j + 1, k + 1) || backtrack(board, word, i, j - 1, k + 1); // 回溯 board[i][j] = t; return res; } }
9 求解数独
求解数独的思路就是对每一个格子所有可能的数字1-9进行穷举，基于此，我们可以写出代码框架：
public void solveSudoku(char[][] board) { backtrack(board, 0, 0); } // 从左上角(r,c)开始回溯求解数组 public void backtrack(char[][] board, int r, int c){ int m = 9; int n = 9; // 对棋盘的每个位置进行穷举 for (int i = r; i < m; i++) { for (int j = c; j < n; j++) { for (char ch = '1'; ch <= '9'; ch ++) { // 做选择 board[i][j] = ch; // 继续穷举下一个 backtrack(board, i, j + 1); // 撤销选择 board[i][j] = '.'; } } } }
如果 j 到最后一列了我们应该从下一行开始继续，如果 i 到最后一行了我们就等于穷举完了所有情况，返回即可。为了减少复杂度，我们可以让backtrack函数返回值为boolean，如果找到一个可行解就返回 true，这样就可以阻止后续的递归。
class Solution { public void solveSudoku(char[][] board) { backtrack(board, 0, 0); } // 从左上角(r,c)开始回溯求解数组 public boolean backtrack(char[][] board, int r, int c){ int m = 9; int n = 9; if(c == n){ // 到最后一列则从下一行开始 return backtrack(board, r + 1, 0); } if(r == m){ return true; } // 对每个位置穷举 for(int i = r; i < m; i ++){ for(int j = c; j < n; j ++){ // 此处已经有数字 if(board[i][j] != '.'){ return backtrack(board, i , j + 1); } for(char ch = '1'; ch <= '9'; ch ++){ if(!isValid(board, i, j, ch)){ continue; } board[i][j] = ch; if(backtrack(board, i, j + 1)){ return true; } board[i][j] = '.'; } // 穷举完仍没找到 return false; } } return false; } public boolean isValid(char[][] board, int r, int c, char ch){ for(int i = 0; i < 9; i ++){ // 判断行是否有重复数字 if(board[r][i] == ch){ return false; } // 判断列是否有重复数字 if(board[i][c] == ch){ return false; } // 判断3×3区域内是否有重复数字 if(board[(r/3)*3 + i/3][(c/3)*3 + i%3] == ch){ return false; } } return true; } }
10 总结
回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作。
写回溯函数时，需要维护走过的路径和当前可以做的选择列表，当满足结束条件时，将路径记入结果集。
