47 全排列II

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

示例 1：

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

题解

这题要做去重，那么就是利用used数组，其次是否能够利用used数组做树层上的去重要看是否能够排序。如果能排序，那么和子集问题或者组合总和问题类似做去重。

验证是否可以去重， 假设数据是 [2,1,1]。那么结果应该是 [2,1,1], [1,2,1], [1,1,2]。如果是[1,1,2]结果也是一样。因为取得顺序并不影响最后的结果。所以这题可以做排序。

排序后去重

var permuteUnique = function (nums) {
    var results = []
    var permuteUniqueInner = function (nums, currentResults, used) {
        if (currentResults.length === nums.length) {
            results.push(currentResults)
            return
        }

        for (let i = 0; i < nums.length; i++) {
            //如果被选过，则不能再次入选
            if (used[i] === true) {
                continue;
            }
            //同层如果有相同的值则跳过
            if (i > 0 && nums[i] === nums[i - 1] && used[i - 1] === false) {
                continue;
            }
            used[i] = true
            permuteUniqueInner(nums, [...currentResults, nums[i]], used)
            used[i] = false
        }
    }

    //定义used 数组
    var used = Array(nums.length).fill(false)

    //必须排序才能用
    nums.sort()

    permuteUniqueInner(nums, [], used)

    return results
};

利用数组或者set来记录本层用过的数字

那么同时我们也可以利用记录当前层的数组（类似于递增子序列）来避免选择同层重复的数字。

var permuteUnique = function (nums) {
    var results = []
    var permuteUniqueInner = function (nums, currentResults, used) {
        if (currentResults.length === nums.length) {
            results.push(currentResults)
            return
        }

        //记录当前层使用过的数字
        const usedInCurrentForLoop = []
        for (let i = 0; i < nums.length; i++) {
            if (used[i] === true) {
                continue;
            }
            //是否有使用过的数字
            const hasUsedInCurrentForLoop = usedInCurrentForLoop.filter(one => one === nums[i]).length
            if (hasUsedInCurrentForLoop) {
                continue;
            }
            used[i] = true
            //记录一层用的数字
            usedInCurrentForLoop.push(nums[i])
            permuteUniqueInner(nums, [...currentResults, nums[i]], used)
            used[i] = false
        }
    }

    //used数组还是用来判断是否选择过
    var used = Array(nums.length).fill(false)

    permuteUniqueInner(nums, [], used)

    return results
};