1. 排列问题

题目

LeetCode46 给定一个没有重复数字的序列，返回其所有可能的全排列，

思路

排列问题的思路同样使用与字母大小写全排列LeetCode784。

元素在使用过一次的时候，在图中第二层的时候，还会再被使用，所以能用startIndex了，使用used[i]数组来标记已经选择的元素。过程如图示。

回溯要注意横向和纵向问题，for是横向，递归是纵向

终止条件：收集元素的数组大小和nums数组的大小一样大的时候，就找到了一个全排列

代码

    /*** 排列问题，同样适用于字母大小写全排列*/List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();boolean[] used;public  List<List<Integer>> permure(int[] nums){if (nums.length == 0){return res;}used = new boolean[nums.length];psermuteHelper(nums);return res;}private  void psermuteHelper(int[] nums) {if (path.size() == nums.length){res.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {//为true的时候代表再纵向被使用过，纵向第一条元素出来的时候，会转为falseif (used[i]){continue;}used[i] = true;path.add(nums[i]);psermuteHelper(nums);path.removeLast();used[i] = false;}}

2. 单词搜索

题目

LeetCode79 给定一个m x n 二维字符网格board和一个字符串单词。如果word存在在网格中，返回true，否则返回false。

单词必须按照字母顺序，通过相邻单元格内的字母构成，其中"相邻 "单元格是那些水平相邻或垂直相邻的单元格，同一个单元格内的字母不允许重复使用。

思路

从上到下，从左到右，还是横向和纵向问题，每个坐标递归调用check（i,j,k)函数，i,j表示网格坐标，k表示word的第k个坐标，如果能搜索到返回true，否则返回false，check的终止条件有两种情况

1. 如果i,j位置的字符和字符串位置k的字符不相等，则这条搜索路径返回失败。
2. 如果搜索到了字符串的结尾，则找到了网格中的一条路径，这条路径上的字符正好可以组成字符串s。

两层for循环分别纵向和横向遍历寻找第一个满足的字符，然后再递归寻找下一个

代码

    public boolean exist(char[][] board,String word){char[] words = word.toCharArray();for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (dfs(board,words,i,j,0)) return true;}}return false;}boolean dfs(char[][] board, char[] word, int i, int j, int k){//坐标越界if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]){return false;}//单词长度找完的时候if (k == word.length - 1){return true;}//转化为十进制0存储在ch中，十进制0对应的ASCII码中的字符即是NULLboard[i][j] = '\0';boolean res = dfs(board,word,i + 1,j, k + 1) || dfs(board,word,i - 1,j, k + 1) ||dfs(board,word,i ,j + 1, k + 1)|| dfs(board,word,i ,j - 1, k + 1);board[i][j] = word[k];return res;}