一天一大 lee(全排列 II)难度:中等-Day20200918

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

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
  let _result = [],
    inList = new Map()
  function helper(item) {
    if (item.length === nums.length) {
      _result.push([...item])
      return
    }
    for (let i = 0; i < nums.length; i++) {
      // 增加重复元素判断，如果元素与上一个相邻元素相同，那么这两个相邻元素只有一个可以参与位置的选择-回溯
      if (inList.has(i) || (i > 0 && nums[i] === nums[i - 1] && !inList.has(i-1))) continue
      item.push(nums[i])
      inList.set(i, true)
      helper(item)
      // 回溯-释放上面被在该位置选择的元素尝试在该位置选择其他元素
      item.pop()
      inList.delete(i)
    }
  }
   if (nums.length < 2) return nums.length === 1 ? [nums]: _result
  //  排序是重复元素相邻
  nums.sort((a, b) => a - b)
  helper([])
  return _result
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
  let _result = []
  if (nums.length < 2) return nums.length === 1 ? [nums]: _result
  function helper(index) {
    if (index === nums.length) {
      _result.push([...nums])
      return
    }
    let map = new Map();
    for (let i = index; i < nums.length; i++) {
      // 一轮交换(一个新位置)中只有未交换过的元素才能参与交换
      if(!map.has(nums[i])) {
        map.set(nums[i], true);
        // 逐个与当前索引位元素交换
        swap(nums, i, index)
        // 进行后续交换
        helper(index + 1)
        // 回溯上一次交换，让下一个位置的交换在上一次未交换的基础上开始
        swap(nums, i, index)
      }
    }
  }
  // 替换指定位置两个数
  function swap(a, i, j) {
    var tmp = a[i]
    a[i] = a[j]
    a[j] = tmp
  }
  helper(0)
  return _result
}