【LeetCode 47】全排列 II

野性酷女 2022-12-06 04:25 134阅读 0赞

#### 题目描述 ####

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

示例:

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

#### 解题思路 ####

这个题目和[【LeetCode 46】全排列][LeetCode 46]相似，只是这到题目中的元素可能是重复的，下面以题目中给的\[1，1，2\]为例：  
![在这里插入图片描述][20200912151118586.png]  
红色部分是需要剪掉的枝。这些路径上包含重复和元素和重复的结果。

首先，我们需要对数组元素进行排序，便于后面前后两个元素进行对比。其他步骤和46题完全一致。只是剪枝的判断条件不一样。

最关键的就是下面这句代码：

if(arr[i] || (i > 0 && !arr[i-1] && nums[i] === nums[i-1])) continue;

*  在每次遍历时，arr标记已使用的情况，所以如果`arr[i]`存在，说明已经遍历过，直接跳过；
 *  `[1,1,2]`是三次遍历的的结果，每一次遍历完后arr所有值都会为false，所以就有了`!arr[i-1] && nums[i] === nums[i-1]`，也就是说，比方第一次遍历了第一个1；第二次，首先遍历了第一个1，在遇到第二个1时，发现和第一个一样，就直接跳过了。

#### 代码实现 ####

/** * @param {number[]} nums * @return {number[][]} */
    var permuteUnique = function(nums) { 
        const res = []
        nums = nums.sort()
        let arr = []
        
        const dfs = (path) => { 
            if(path.length === nums.length){ 
                res.push([...path])
            }
            for(let i = 0; i < nums.length; i++){ 
                if(arr[i] || (i > 0 && !arr[i-1] && nums[i] === nums[i-1])) continue
                
    			path.push(nums[i])
                arr[i] = true
                dfs(path)
                path.pop()
                arr[i] = false
            }
        }
        dfs([])
        return res
    
    };

#### 提交结果 ####

![在这里插入图片描述][20200912152627784.png]

[LeetCode 46]: https://cuggz.blog.csdn.net/article/details/108549192
[20200912151118586.png]: /images/20221123/82cfcc3adf8d4f9bb221cd510036b375.png?
[20200912152627784.png]: /images/20221123/d4d84086ea6844e98a90635ef8b42979.png?