回溯

是什么

1. 一种算法思维
2. 一种渐进式寻找并构建问题解决形式的策略
3. 会先从一个可能的动作开始解决问题，如果不行，就回溯并抉择另一个动作，直到将问题解决

案例: 鬼吹灯寻路

leetcode

46 全排列

代码

    function premute(nums) {
      // 1. 设置后果集
      const res = []
      // 2. 回溯
      const backtrack = (path) => {
        // 2.1 设置回溯终止条件
        if(path.length === nums.length){
          // 2.1.1 推入后果集
          res.push(path)
          // 2.1.2 终止递归
          return;
        }
        // 2.2 遍历数组
        nums.forEach(n => {let pathIncludesN = path.includes(n)
          // 2.2.1 必须是不存在 数组 中的元素
          if(pathIncludesN){return}
          // 2.2.2 本地递归条件
          let pathConcatN = path.concat(n)
          // 2.2.3 进一步递归
          backtrack(pathConcatN)
        })
      }
      backtrack([])
      // 3. 返回后果
      return res;
    }
    var nums = [1, 2]
    // var nums = [1, 2,3]
    var result = premute(nums)
    console.log('result', result)

复杂度剖析

• 工夫复杂度：O(n∗n!)，其中 n 为序列的长度
• 空间复杂度：O(n)，其中 n 为序列的长度。除答案数组以外，递归函数在递归过程中须要为每一层递归函数调配栈空间，所以这里须要额定的空间且该空间取决于递归的深度，这里可知递归调用深度为 O(n)。