全排列（LeetCode 46）

题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。

示例：
输入 [1, 2, 3]
输出 [
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1],
]
思路分析：
这个题给了我们 n 个数组成的数组，让我们把所有的排列形式都列举出来，根据示例，我们总共有 3 个坑位要填，我们把可能的情况都列出来，发现我们的思维是一个树形结构

要获取某一种排列形式，我们需要在树中进行DFS，因此我们决定使用递归来做题
递归需要确定：

递归式：填完一层填下一层
递归边界：三个坑位都填满了

另外，为了填数的时候不重复，需要维护一个 Map ，填过的数就打上标签

var permute = function(nums){ // 全排列问题
  const res = []
  // 记录当前排列内容 
  const curr = []
  // 记录访问过的数字
  const visited = {}
  const len = nums.length
  // 第 0 层开始
  dfs(0)
  function dfs(nth){
    // 到第 3 层结束，不再往下执行
    if(nth === len){ // 坑位已满
      // push curr 的拷贝
      // res.push([...curr]) 也行
      res.push(curr.slice()) 
      return
    }
    for(let i=0 ;i < len; i++){
      if(!visited[nums[i]]){
        // 数字使用了，要打上标签
        visited[nums[i]] = 1
        curr.push(nums[i])
        // 基于这个排列往下一个坑位走
        dfs(nth + 1)
        // 消除标签
        visited[nums[i]] = 0
        // nums[i]让出当前坑位，换for循环里的其他取值
        curr.pop()
      }
    }
  }
  return res
}

注意:

当前路径搜索完成以后，数字 pop 让出坑位的时候，别忘了 visited 中数字状态也要还原为未使用
当走到递归边界时，一个完整的排列也生成了。将这个完整排列推入结果数组时，要使用res.push(curr.slice())，因为全局只有一个curr，curr 的值会随着 dfs 不断的更新，上面写法是 push 一个 curr 的拷贝。或者使用res.push([ ...curr ])也可以
子集（LeetCode 78）

题目描述：：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。

示例：
输入 nums = [1, 2, 3]
输出 [
[],
[1],
[1,2],
[1,2,3],
[1,3],
[2],
[2,3],
[3]
]
思路分析：
这个题给了我们 n 个数组成的数组，让我们把所有的组合形式都列举出来。根据示例与题目1相比，我们发现这次坑位是不一定的了，最小0个，但最大还是三个，为了使组合里没有重复的元素，我们从数组取数的时候严格按照索引顺序
递归与回溯 - 图2
同样在树中DFS，我们使用递归来解题：

递归式：填完一层填下一层，但是不是连续的填满三层了

递归边界：索引在数组中取不到元素了

var subsets = function(nums){
const res = []
const len = nums.length
// 记录当前组合
const subset = []
dfs(0)
function dfs(index){
  // 每次进入，都意味着组合要更新了，先把之前的组合放到 res 里
  res.push(subset.slice())
  // 递归终止条件，最多用到坑位3
  // 这句if可以不写，后面for循环里一样判断
  if(index === len) return
  // i的初始值是index,表示前面的坑位都没有数字
  for(let i=index; i< len; i++){
    subset.push(nums[i])
    dfs(i+1)
    subset.pop()
  }
}
return res
}

组合（及时回溯，即为剪枝）(LeetCode 77)

题目描述：给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例：
输入：n=4, k=2
输出：[ [1,2], [1,3], [1,4], [2,3], [2,4], [3,4] ]
思路分析：
这是一个复杂化的组合问题，它加了限定条件——组合里面个数为k，
这就意味着在DFS的过程中，一旦组合的个数满足要求了，就会停止往下继续搜索，这个过程也叫做剪枝
要做到剪枝就要修改递归边界：

递归边界：组合内数字个数达到k

此外，原来的组合问题每往下搜索一层就要对结果数组更新，而限定组合问题只要到递归边界才更新

const combine = function (n, k) {
  const res = []
  const subset = []
  dfs(1)
  function dfs(index) {
    // 递归的终止条件
    if (subset.length === k) {
      res.push(subset.slice())
      return
    }
    for (let i = index; i <= n; i++) {
      subset.push(i)
      dfs(i+1)
      subset.pop()
    }
  }
  return res
}

递归与回溯思想

DFS 采用了递归思想进行枚举，回溯则是涉及到剪枝操作的 DFS——本质就是加了限定条件的递归
关于递归回溯类的题目有一个解题模板：
首先判断使用场景，然后套用模板后填充：

使用场景

题目中一般有多个解，并且要求我们详细的把每一种解的情况列出来（如果不问解的内容，而问解的个数，通常是用动态规划）
递归与回溯的过程就是穷举的过程，题目中要求枚举每一种解，八九不离十就是要用递归与回溯

套用模板

递归与回溯的重点在于确定递归边界和递归式，模板如下

function xxx(入参) {
  前期的变量定义、缓存等准备工作 

  // 定义路径栈
  const path = []

  // 进入 dfs
  dfs(起点) 

  // 定义 dfs
  dfs(递归参数) {
    if(到达了递归边界) {
      结合题意处理边界逻辑，往往和 path 内容有关
      return   
    }

    // 注意这里也可能不是 for，视题意决定
    for(遍历坑位的可选值) {
      path.push(当前选中值)
      处理下一个坑位本身的相关逻辑 dfs(...)
      path.pop()
    }
  }
}

如果隐约觉得这道题用递归回溯来解可能有戏，却一时间没办法明确具体的解法，可以尝试先把模板框架写出来，然后结合题意去调整和填充伪代码的内容

递归与回溯

全排列（LeetCode 46）

子集（LeetCode 78）

组合（及时回溯，即为剪枝）(LeetCode 77)

递归与回溯思想

使用场景

套用模板