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

思路

  1. 《全排列 》 的进阶版，需要去重
  2. 保证新插入的元素位置不大于已存在的相同元素的下标即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var permuteUnique = function (nums) {
  nums.sort((a, b) => a - b)
  let prevVal = null
  let curItems = [[]]
  for (const val of nums) {
    const nextItems = []
    for (const items of curItems) {
      let end = items.length
      if (val === prevVal) {
        end = items.indexOf(val)
      }
      for (let j = 0; j <= end; ++j) {
        const curVals = [...items]
        curVals.splice(j, 0, val)
        nextItems.push(curVals)
      }
    }
    prevVal = val
    curItems = nextItems
  }
  return curItems
}