递归和回溯

当分析题目有重复逻辑就可以考虑递归

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。

或者说涉及剪枝操作的递归，我们一般称之为回溯

递归和回溯是同时出现的概念

模板：


function xxx(入参) {
  前期的变量定义、缓存等准备工作 
  
  // 定义路径栈
  const path = []
  
  // 进入 dfs
  dfs(起点) 
  
  // 定义 dfs
  dfs(递归参数) {
    if(到达了递归边界) {
      结合题意处理边界逻辑，往往和 path 内容有关
      return   
    }
    
    // 注意这里也可能不是 for，视题意决定
    for(遍历坑位的可选值) {
      path.push(当前选中值)
      处理坑位本身的相关逻辑
      path.pop()
    }
  }
}

举个例子

46. 全排列

给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。


输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

其实就是三个坑位进行遍历

标记法


/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// 入参是一个数组
const permute = function(nums) {
  // 缓存数组的长度
  const len = nums.length
  // curr 变量用来记录当前的排列内容
  const curr = []
  // res 用来记录所有的排列顺序
  const res = []
  // visited 用来避免重复使用同一个数字
  const visited = {}
  // 定义 dfs 函数，入参是坑位的索引（从 0 计数）
  function dfs(nth) {
      // 若遍历到了不存在的坑位（第 len+1 个），则触碰递归边界返回
      if(nth === len) {
          // 此时前 len 个坑位已经填满，将对应的排列记录下来
          res.push(curr.slice())
          return 
      }
      // 检查手里剩下的数字有哪些
      for(let i=0;i<len;i++) {
          // 若 nums[i] 之前没被其它坑位用过，则可以理解为“这个数字剩下了”
          if(!visited[nums[i]]) {
              // 给 nums[i] 打个“已用过”的标
              visited[nums[i]] = 1
              // 将nums[i]推入当前排列
              curr.push(nums[i])
              // 基于这个排列继续往下一个坑走去
              dfs(nth+1) 
              // nums[i]让出当前坑位
              curr.pop()
              // 下掉“已用过”标识
              visited[nums[i]] = 0
          }
      }
  }
  // 从索引为 0 的坑位（也就是第一个坑位）开始 dfs
  dfs(0)
  return res
};

重新组合数组法


[1,2,3]的全排列就是先确定1，再加上[2,3]的全排列

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
 // 缓存数组的长度
  const len = nums.length
  // curr 变量用来记录当前的排列内容
  const res = []
  // 定义 dfs 函数，入参是坑位的索引（从 0 计数）
  function dfs(array,cur=[]) {
      // 若遍历到了不存在的坑位（第 len+1 个），则触碰递归边界返回
      if(cur.length === len) {
          // 此时前 len 个坑位已经填满，将对应的排列记录下来
          res.push(cur)
          return 
      }
      // 检查手里剩下的数字有哪些
      for(let i=0;i<array.length;i++) {
          // 若 nums[i] 之前没被其它坑位用过，则可以理解为“这个数字剩下了”
              // 给 nums[i] 打个“已用过”的标
        const newArray = [...array.slice(0,i),...array.slice(i+1,len)]
        dfs(newArray,[...cur,array[i]])
      }
  }
  dfs(nums)
  return res
};