47. 全排列 II

[wengzc]

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

示例:

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

题目链接：https://leetcode-cn.com/problems/permutations-ii

[wengzc]

思路分析：回溯法

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
    let len = nums.length
    nums.sort((a, b) => {
        return a - b
    })
    let res = []
    let cur = []
    let map = {}
    let backtrack = nth => {
        if (nth === len) {
            res.push(cur.slice())
            return
        }
        for (let i = 0; i < len; i++) {
            // 回溯剪枝
            if (i > 0 && nums[i] === nums[i - 1] && !map[i - 1]) continue
            if (!map[i]) {
                // 写成map[i]，不要写成map[nums[i]]，因为有重复值的话，map[nums[i]]不能准确判断索引i位置的值
                map[i] = true
                cur.push(nums[i])
                backtrack(nth + 1)
                cur.pop()
                map[i] = false
            }
        }
    }
    backtrack(0)
    return res
};