【进阶篇 - Day 51】 2020-12-21 - 47. 全排列 II（05.剪枝 ）

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

示例 1：

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

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

提示：

1 ⇐ nums.length ⇐ 8
-10 ⇐ nums[i] ⇐ 10

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的回答

https://github.com/leetcode-pp/91alg-2/issues/81#issuecomment-748786213

解法一

时空复杂度

时间复杂度：O(n^2)

空间复杂度: O(n)

难点在如何去重，用一个 vis 记录已经访问的数组，取到想要的数组后，将 vis 置空

var permuteUnique = function (nums) {
    const res = []
    let vis = Array(nums.length).fill(false)
    nums = nums.sort((a, b) => a - b)
    function dfs(index, temp = []) {
        if (index === nums.length) {
            res.push([...temp])
            return
        }
        for (let i = 0; i < nums.length; i++) {
            // 两个相邻值，且不是同时访问了
            if (nums[i - 1] === nums[i] && !vis[i - 1]) continue
            // 访问过,跳出
            if (vis[i]) continue
            temp.push(nums[i])
            vis[i] = true
            dfs(index + 1, temp)
            vis[i] = false
            temp.pop()
        }
    }
    dfs(0)
    return res
};

参考回答