回溯算法秒杀所有排列/组合/子集问题

形式一：元素无重复不可复选 套路 形式二：元素可重复不可复选 先排序在剪枝 形式三：元素无重复可复选

排列

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
}

组合

77. 组合 (opens new window)

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function (n, k) {
  const path = []
  const res = []
  const traverse = (start) => {
    // 组合的话就判断长度
    if (path.length === k) {
      res.push([...path])
    }
    for (let i = start; i < n; i++) {
      path.push(i + 1)
      traverse(i + 1)
      path.pop()
    }
  }
  traverse(0)
  return res
}

子集

78. 子集 (opens new window)

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  const res = []
  const path = [] // 记录路径
  // 核心 用start来控制剩余选项
  const traverse = (start) => {
    res.push([...path])
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i])
      traverse(i + 1)
      path.pop()
    }
  }
  traverse(0)
  return res
}

90. 子集 II (opens new window) （可重复不可以复选子集问题）

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
  const new_nums = nums.sort()
  const path = []
  const res = []
  const traverse = (start) => {
    res.push([...path])
    for (let i = start; i < new_nums.length; i++) {
      if (i > start && new_nums[i] === new_nums[i - 1]) {
        continue
      }
      path.push(nums[i])
      traverse(i + 1)
      path.pop()
    }
  }
  traverse(0)
  return res
}