回溯

回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」

理解 3 个要点：

1. 路径：已经做出的选择

2. 选择列表：你当前可以做的选择

3. 结束条件： 到达决策树底层，无法再做出选择的条件。

result = []
function backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

46. 全排列 (opens new window)

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const path = []
  const res = []
  const selected = []
  const traverse = () => {
    if (path.length === nums.length) {
      res.push([...path])
    }
    // // 可以使用的列表
    for (let select of nums) {
      // 已经选择的数字不需要再选了
      if (selected.includes(select)) {
        continue
      }
      // 选择一个数字
      path.push(select)
      selected.push(select)

      traverse()
      // 后序取消选择
      path.pop()
      selected.pop()
    }
  }

  traverse()

  return res
}

51.N 皇后 (opens new window)

17. 电话号码的字母组合 (opens new window)

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  const number = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
  const path = []
  const res = []
  if (!digits.length) return res
  const traverse = (start) => {
    if (path.length === digits.length) {
      res.push([...path].join(''))
      return
    }
    for (let i of number[digits[start]]) {
      path.push(i)
      traverse(start + 1)
      path.pop()
    }
  }

  traverse(0)

  return res
}