题目：全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列
输入：nums = [1,2,3] //目标数组
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
用回溯算法解答，解题思路为：
1、递归函数，结束条件：临时数组(temp)长度==目标数组长度
2、临时数组(temp)，往里加目标数组的元素，重复的不要
3、所以for循环，尝试向临时数组加入目标[0] 目标[1] 目标[2]
4、重要的是在递归返回后，从temp弹出一个元素；打印顺序为[1] [1,2] [1,2,3] [1,2][1] 这就是回溯
5、此时再次循环则是[1,3] [1,3,2] [1,3] [1] [ ]
举例1个简单的[1,2]
let cs = 0
let list = []
function test(temp, paramArr) {
cs++
if (temp.length === paramArr.length) {
console.log(`递归第${cs}次-符合条件-结束`);
cs-- //递归到头了，准备回去，所以cs--
list.push([...temp])
return
}
for (let i = 0; i < paramArr.length; i++) {
if (temp.includes(paramArr[i])) {
continue;
}
temp.push(paramArr[i])
console.log(`递归第${cs}次的f${i}`, temp);
test(temp, paramArr)
temp.pop()
console.log(`递归第${cs}次的f${i}-弹出后`, temp);
}
cs-- //本函数执行完毕，所以cs--
}
const paramArr = [1, 2]
test([], paramArr)
console.log("list:", list); //[ [ 1, 2 ], [ 2, 1 ] ]
递归第1次的f0 [ 1 ]
递归第2次的f1 [ 1, 2 ]
递归第3次-符合条件-结束
递归第2次的f1-弹出后 [ 1 ] //第二次调用函数未结束，所以接着走到函数底部
递归第1次的f0-弹出后 []
递归第1次的f1 [ 2 ] //执行第一次的for循环 i=1时
递归第2次的f0 [ 2, 1 ]
递归第3次-符合条件-结束
递归第2次的f0-弹出后 [ 2 ]
递归第1次的f1-弹出后 []
题目：单词搜索
给定一个 二维字符网格 board 和一个字符串单词 word
如果 word 存在于网格中，返回 true ；否则，返回 false
单词必须按照字母顺序，通过相邻的单元格内的字母构成
二维数组： board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],
目标： word = "ABCCED"
解题思路：
1、双循环得出 行和列坐标，让每个坐标都做为开头 来尝试查找
2、找到第一个，然后上下左右接着找，为了避免又把第1个元素当结果，暂时用null代替
3、没找到则结束这个坐标的操作，把null也回溯恢复，然后开始下一个坐标的查找
var exist = function (board, word) {
//设置行列数
let row = board.length;
let col = board[0].length;
//双循环，每个坐标都尝试 作目标的第1元素
for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
//从宫格图中第一个开始找(i,j)，找目标第一个字母（word[0]）
const ret = find(i, j, 0); //返回true或false
if (ret) {
return ret;
}
}
}
return false; //结束了都没找到，就false
//递归函数,第1个元素符合就接着内部再递归find上下左右找第2元素
function find(r, c, cur) {
if (r >= row || r < 0) return false;
if (c >= col || c < 0) return false;
if (board[r][c] !== word[cur]) return false; //不是目标元素则false
//执行到这，说明rc坐标是目标元素；
//先判断，如果是最后一个也找到了，返true结束
if (cur == word.length - 1) return true;
let letter = board[r][c]; //赋给临时变量
board[r][c] = null; //用null替换做标记，避免下一个找上下左右时重复
//进行下一步，上下左右查找
//如:[0][0]是目标第1个元素，这里接着find找[0][1],[1][0]
//没找到返回false，结束所有find，进入双for中的[0][1]
const ret =
find(r - 1, c, cur + 1) ||
find(r + 1, c, cur + 1) ||
find(r, c - 1, cur + 1) ||
find(r, c + 1, cur + 1);
//用null做标记是避免重复，但双for的find结束就需要恢复
board[r][c] = letter;
return ret;
}
};
这里用回溯是避免重复，导致答案错误
