47-全排列II.md

题目描述

全排列II

题目简述

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

示例 1：

输入：nums = [1,1,2] 输出：

• [[1,1,2],
• [1,2,1],
• [2,1,1]]

分类

中等 回溯

思路

思路1

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
  const res = []
  const filterMap = new Array(nums.length).fill().map((i, index) => index)
  // sort
  nums.sort((x, y) => x - y)
  function backTrack(arr) {
    if (arr.length === nums.length) {
      res.push([...arr])
      return
    }
    const _arr = filterMap.filter(i => i !== -1)
    for (let i = 0; i < _arr.length; i++) {
      // 相同
      if (i && nums[_arr[i]] === nums[_arr[i - 1]]) {
        continue
      }
      const temp = _arr[i]
      arr.push(nums[_arr[i]])
      filterMap[_arr[i]] = -1
      backTrack(arr)
      arr.pop()
      filterMap[_arr[i]] = temp
    }
  }
  backTrack([])
  return res
};

• 问题分析
  • 回溯思路：有一个和nums一样长的数组arr，我们从arr第一位开始填充。
    • 填充规则1:两个相同的数字不能填入同一个位置；
    • 因此，我们先将nums排序，在依次遍历时，相同的数字是连续的，只需要避免和上次的值相同即可。
    • 填充规则2:已经填充的数字不能再进行填充
    • 因此，我们声明一个filterMap用于储存哪些数字是已经填充了的，形如[0,1,2,3,4,5,6]，只要该位不是-1,那么该位就是未使用的
  • 回溯终止条件：arr.length === nums.length就说明nums的数字都已经填充到arr中
  • 回溯可能性查找：由于填充规则2的限制，我们只对未填充的数字进行遍历，且每次进行判断，不填入重复的数字。
  • 递归前，将数字填入arr，将该位数字置为-1；递归后，删除arr末位，回填该数字。