题目

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

1 <= nums.length <= 8

-10 <= nums[i] <= 10

示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
题解链接

思路

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    // 结果数组 
    let result = []

    // 从第一个开始执行
    dfs(0)

    // 返回结果，数组的数组
    return result

    // 深度优先遍历
    function dfs(index) {
        // 递归退出条件：深度达到数组长度
        if (index === nums.length) {
            result.push([...nums])
            return
        }

        // 利用集合特性去重
        let set = new Set()
        for (let i = index; i < nums.length; i++) {
            if (!set.has(nums[i])) {
                set.add(nums[i])
                swap(index, i)
                dfs(index + 1)
                swap(index, i) //到头了，换回来
            }
        }
    }

    // 交换数组两个下标对应的值
    function swap(a, b) {
        let temp = nums[a]
        nums[a] = nums[b]
        nums[b] = temp
    }
};