全排列.md

全排列

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

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

回溯算法

/**
 * @param {number[]} list
 * @return {number[][]}
 */
var permute = function(list) {
  const res = []
  const backtrack = function (nums, track) {
    if (track.length === nums.length) {
      // track是引用对象，需要生成新的对象
      res.push([...track])
      return
    }
    for (let i = 0; i < nums.length; i++) {
      // 已经做过选择的，跳过
      if (track.includes(nums[i])) {
        continue
      }
      // 做选择
      track.push(nums[i])
      // 进入下一个决策
      backtrack(nums, track)
      // 撤销选择
      track.pop()
    }
  }
  backtrack(list, [])
  return res
}

标准解法

/**
 * @param {number[]} list
 * @return {number[][]}
 */
var permute = function(list) {
  const res = []
  const memo = []
  const backtrack = function (nums, track) {
    if (track.length === nums.length) {
      // track是引用对象，需要生成新的对象
      res.push([...track])
      return
    }
    for (let i = 0; i < nums.length; i++) {
      // 已经做过选择的，跳过
      if (memo[nums[i]]) {
        continue
      }
      // 做选择
      memo[nums[i]] = true
      track.push(nums[i])
      // 进入下一个决策
      backtrack(nums, track)
      memo[nums[i]] = false
      // 撤销选择
      track.pop()
    }
  }
  backtrack(list, [])
  return res
}

进阶-包含重复数字的全排列

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

题解

var permuteUnique = function(list) {
  const res = []
  const cache = {}
  /**
   * @param nums-可选列表
   * @param track-已做列表
   */
  const backtrack = function (nums, track) {
    if (track.length === list.length) {
      // track是引用对象，需要生成新的对象
      res.push([...track])
      return
    }
    for (let i = 0; i < nums.length; i++) {
      // 重复数字，下一个
      if (cache[`${track}-${nums.length}-${nums[i]}`]) {
        continue
      } else {
        // 记录数字走过的层级
        cache[`${track}-${nums.length}-${nums[i]}`] = true
      }
      // 做选择
      const val = nums.splice(i, 1)[0]
      track.push(val)
      // 进入下一个决策
      backtrack(nums, track)
      // 撤销选择
      nums.splice(i, 0, track.pop())
    }
  }
  const nums = [...list]
  backtrack(nums, [])
  return res
}

标准解法

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(list) {
  const res = []
  const caches = []
  // 先排序
  list.sort((x, y) => x - y);
  /**
   * @param nums-可选列表
   * @param track-已做列表
   */
  const backtrack = function (track) {
    if (track.length === list.length) {
      // track是引用对象，需要生成新的对象
      res.push([...track])
      return
    }
    for (let i = 0; i < list.length; i++) {
      // 相邻两个相同的数，不走同一个策略，达到去重效果
      if (caches[i] || (list[i] === list[i-1] && caches[i-1])) {
        continue
      }
      caches[i] = true
      // 做选择
      track.push(list[i])
      // 进入下一个决策
      backtrack(track)
      caches[i] = false
      track.pop()
    }
  }

  backtrack([])
  return res
}