实现数组的全排列和单词搜索
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例
给定 numbs = [1,2,3];返回[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
思路
回溯法通常是构造一颗生成树，生成树排列法的核心思想为： 遍历需要全排列的数组，不断选择元素，将不同的数字生成一颗树，如果数组中待选择的结点数为 0，则完成一种全排列。
详解
从上面的思路中，我们可以抽象出全排列函数的步骤：
1. 遍历需要全排列的数组，取出不同位置的数字，创建以对应位置数字为根节点的树。2. 遍历剩下的数组，选出一个数字，将该数字挂在生成的树上。3. 重复第二步操作直到剩余数字数组的长度为0，表明完成了全排列，将生成的树存入排序结果数组中。
举个例子：输入数组为 [1, 2, 3]，首先选择 1 为根节点，剩余数组为 [2, 3]，继续选择 2 作为下一个结点，剩余数组为 [ 3 ]，那么选择 3 为最后一个结点，那么 [1, 2, 3] 组成一种全排列情况。 我们回溯到第二步剩余数组，选择 3 为第二个结点，那么剩余数组为 [ 2 ]，选择后完成 [1, 3, 2] 这种全排列情况。后续依次固定 2，3 为根结点，列出所有可能。
从上述内容中可以看出，生成初始树后就是一个 截取数组 -> 设置节点，继续 截取节点 -> 设置节点 的递归过程了。那么我们是否可以将第一步的操作合并到我们的递归函数中呢？
既然我们递归的操作是截取数字，并将对应的数字与目标树结合。那么我们可以将第一步看为数字和空树结合。
那么我们递归函数的参数就确定为：
剩余的数组
现有的顺序树
递归函数的逻辑也可以收敛为：
遍历需要全排列的数组，将不同位置的数字与目前树结合起来
重复该操作直到需要全排列的数组长度为 0，即表明完成了全排列。
代码
const permute = function (numbs) {const allSortResult = []; // 设置结果数组function recursion (restArr, tempResult) {for (let index = 0; index < restArr.length; index++) {// 获取不同位置的数字const insertNumb = restArr[index];// 将不同位置的数字与现有的顺序树相结合const nextTempResult = [...tempResult, insertNumb];/*** 判断传入的数组长度* 大于1:* 继续递归，参数分别为：* 1. 除去当前数字外的数组* 2. 新生成的树* 等于1(不会出现小于1的情况):* 表明已经结合到了最后一个节点，将生成的顺序树推送到结果数组中*/if (restArr.length > 1) {recursion(restArr.filter(resetNumb => resetNumb !== insertNumb),nextTempResult);} else {allSortResult.push(nextTempResult);}}}// 调用递归方法，开始生成顺序树recursion(numbs, []);// 返回全排列结果return allSortResult;};
复杂度分析
时间复杂度：
空间复杂度：
思路
插值排列法的核心思想为： 遍历需要全排列的数组，将不同位置的数字抽离出来，插入到剩余数组的不同位置，即可得到该数字与另一个数组的全排列结果。 将一个固定的数字，插入到另一个数组的全排列结果的不同位置， 遍历需要全排列的数组，将不同的数字连接到不同的树上 继续全排列剩下的数组与生成的树，当剩余数组长度为0时，表明完成了全排列。
详解
从上面的思路中，我们可以抽象出插值排序全排列方法的具体实现：
首先处理特殊情况。如果传入排列的数组长度为1，直接返回该数组。否则进行下面的全排列方法
1. 截取传入数组的第 1 位数字，将剩余数组传入获取全排列方法函数，获取剩余数字的全排列结果2. 遍历剩余数字的全排列结果数组并取出各个结果3. 使用循环将截取的数字插入到不同结果(数组)的不同位置，生成新的全排列结果并保存4. 返回全排列结果数组
代码
const permute = function (numbs) {// 设定保存结果变量const result = [];// 如果长度为1，只有一种排列，直接返回if (numbs.length === 1) {return [numbs];} else {// 长度大于1，获取除第一个数字外的数组的全排列结果const allSortList = permute(numbs.slice(1));// 遍历剩余数字的全排列结果数组for (let sortIndex = 0; sortIndex < allSortList.length; sortIndex++) {// 取出不同的全排列结果const currentSort = allSortList[sortIndex];// 将第一个数字插入到不同的位置来生成新的结果，并保存for (let index = 0; index <= currentSort.length; index++) {const tempSort = [...currentSort];tempSort.splice(index, 0, numbs[0]);result.push(tempSort);}}// 返回全排列结果数组return result;}};
复杂度分析：
时间复杂度： 时间复杂度由全排列函数 permute 提供。单个全排列函数中存在两层循环嵌套，因此单次调用的时间复杂度为 当 numbs 长度为 到 2 时调用全排列函数，即调用 次 ; 当 趋近于无限大时， 可以忽略，因此时间复杂度为
空间复杂度：， 在循环体内使用4个变量，空间复杂度为 ，当 趋近于无限大，忽略系数，即为
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例
board =[['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]给定 word = "ABCCED", 返回 `true`.给定 word = "SEE", 返回 `true`.给定 word = "ABCB", 返回 `false`.
思路
题目给的要求水平相邻或垂直相邻的单元格，这与回溯的思想非常相似，简单来说，上下左右都去走一遍，发现不符合要求立即返回。
以题目的示例为例子，从 A 开始，放四个方向试探，如果不匹配，立即换方向
详解
从起点开始，枚举所有的可能性，递归搜索
如果当前字符串匹配，再考虑上下左右 4 个方向，当发现超出边界或者不匹配时，立即结束当前方向的搜索
/*** @param {character[][]} board* @param {string} word* @return {boolean}*/const exist = function (board, word) {const m = board.length;const n = board[0].length;for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (wordSearch(i, j, 0)) {return true;}}}function wordSearch (i, j, k) {// 超出边界或者不匹配时，返回 falseif (i < 0 || j < 0 || i >= m || j >= n || word[k] !== board[i][j]) {return false;}// 找到最后一个字符，返回 true，为递归的终止条件if (k === word.length - 1) {return true;}// 先占位const temp = board[i][j];board[i][j] = '-';// 往四个方向递归搜索，有一个方向匹配就可以了const res = wordSearch(i + 1, j, k + 1) ||wordSearch(i - 1, j, k + 1) ||wordSearch(i, j + 1, k + 1) ||wordSearch(i, j - 1, k + 1);// 四个方向搜索完了释放board[i][j] = temp;return res;}return false;};
复杂度分析
时间复杂度：
和 分别是矩阵的行数和列数。 每个递归函数
wordSearch的调用次数为 ，并且调用了4个递归函数，复杂度为 在 for 循环下，时间复杂度为 。 因此总的时间复杂度为空间复杂度：
每个递归函数的递归深度为 , 空间复杂度为 ，一共调用了4个，因此总的复杂度为
