算法题（回溯）
一、题目
1、括号生成（LC 22）
2、单词搜索（LC 79）
二、题解
1、括号生成（LC 22）
（1）分析
采用回溯的思想解决。递归方法包括 left、right、ans、path、n 五个核心参数，其中 left 与 right 分别记录已使用的左、右括号数量，ans 用于存储所有合法的括号组合结果，path 为固定长度的字符数组，用于暂存单组括号组合，n 为需要生成的括号对数。
递归边界条件：右括号使用次数达到 n，此时左括号必然也使用了 n 次，形成完整合法组合，将 path 转换为字符串加入结果集后回溯至上一层。递归过程中，当左括号使用次数小于 n 时，可向 path 中添加左括号；当右括号使用次数小于左括号时，可添加右括号。一次递归结束也无需恢复现场，因为下一次的获取的括号组合会覆盖上一次的组合。
（2）解答
class Solution { public List<String> generateParenthesis(int n) { //初始化 List<String> ans = new ArrayList<>(); //结果列表，存放最终结果 char[] path = new char[2 * n]; //存放每一种括号组合 dfs(0, 0, ans, path, n); return ans; } //当前使用了left个左括号，right个右括号 public void dfs(int left, int right, List<String> ans, char[] path, int n){ if(right == n){ //path已经放满，获取了一种括号组合，添加到结果列表中 ans.add(new String(path)); return; } if(left < n){ path[left + right] = '('; dfs(left + 1, right, ans, path, n); } if(right < left){ //左括号数要小于右括号数，才可以选择 path[left + right] = ')'; dfs(left, right + 1, ans, path, n); } } }2、单词搜索（LC 79）
（1）分析
使用回溯方法解决。相较于基础回溯算法，这题多了两个参数 i， j 来表示搜索位置，参数 k 表示字符的下标。通过两层循环遍历矩阵的每一个位置，以每个位置作为起点启动深度优先搜索，若某次搜索返回 true，则证明矩阵中存在目标单词，说明board数组中含有Word的字符组合，直接返回最终结果。
递归边界条件：board数组当前位置的字符与word的对应字符不相等，直接返回 false 终止当前分支；如果相等，且 k 值达到字符数组最大下标，说明board数组中含有Word字符的组合，返回true。对于遍历到的每个board数组中的位置，将当前访问的矩阵位置置零作为访问标记，在此次递归过程不能再继续访问，四个方向递归完成后再恢复现场，确保不影响下一次递归。
（2）解答
class Solution { static int[][] dir = {{-1, 0},{1, 0},{0, -1},{0, 1}}; //方向：上下左右 public boolean exist(char[][] board, String word) { //初始化 char[] wordChar = word.toCharArray(); for(int i = 0; i < board.length; i++){ //遍历board中每个元素 for(int j = 0; j < board[i].length; j++){ if(dfs(i,j,0,board,wordChar)){ return true; } } } return false; } public boolean dfs(int i, int j, int k, char[][] board, char[] wordChar){ if(board[i][j] != wordChar[k]){ //当前元素不符合对应字符 return false; } if(k == wordChar.length -1){ //当前元素符合对应字符，且为最大下标 return true; } board[i][j] = 0; //标记当前元素为已使用的 for(int[] d : dir){ //向四个方向递归 int x = i + d[0]; int y = j + d[1]; if(x>=0 && x<board.length && y>=0 && y<board[x].length &&dfs(x,y,k+1,board,wordChar)){ return true; } } board[i][j] = wordChar[k]; //恢复现场 return false; } }