【JS算法】回溯算法

题目：全排列
给定一个不含重复数字的数组 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;
  }
};

这里用回溯是避免重复，导致答案错误