LeetCode - 47 全排列 II

╰+攻爆jí腚メ 2023-09-26 11:14 29阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

--------------------

### 题目来源 ###

[47. 全排列 II - 力扣（LeetCode）][47. _ II - _LeetCode]

### 题目描述 ###

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

### 示例 ###

> **输入：**nums = \[1,1,2\]  
> **输出：**  
> \[\[1,1,2\],  
> \[1,2,1\],  
> \[2,1,1\]\]

> **输入：**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`

### 题目解析 ###

这题和全排列1的区别在于，给定的数组nums中存在重复元素，这样全排列中必然会产生重复的排列，比如nums = \[1,1,2\]的全排列如下

![60333fdfc9cd4bba9683285bf93694c4.png][]

我这里用红色1和黑色1标记出两个1是不同元素。

但是，当前题目要求，全排列中不能出现重复的排列，此时有两种思路：

1.  还是求出所有排列，包括重复排列，最后输出前，过滤掉重复的排列
2.  在深度优先搜索过程中就避免重复排列的求解

方案1肯定是最简单的，但是性能是浪费的。

方案2是较优解，但是该如何实现呢？其实也很简单，全排列1的实现中，我们判断某个层级是否能使用某个元素，靠的是used数组记录元素的使用情况，如果元素使用过了，则当前层级就不能使用。

因此，这里我们只需要改变候选元素的筛选规则即可，在dfs前，我们可以将nums中去重元素的数量计数，比如nums = \[1,1,2\] 可以计数为 count = \{"1"：2， "2"：1\}，即元素1出现了两次，元素2出现了一次。

这样当我们dfs递归生成每个层级的元素时，只在nums = \[...new Set(nums)\]中选择，刷选条件是 count\[num\] > 0。比如第一层级判断count\[1\]=2>0为true，则可以选择1，然后count\[1\]--，然后第二层选择1前同样判断count\[1\]=1>0，则可以选择1，然后count\[1\]--，到了第三层如果依旧想选择1，则继续判断count\[1\]=0 ≯ 0，则不能选择1，转而选择判断count\[2\]=1>0，因此只能选择2。

### 算法源码 ###

/**
     * @param {number[]} nums
     * @return {number[][]}
     */
    var permuteUnique = function(nums) {
        let count = {}
        nums.forEach(num => {
            count[num] ? count[num]++ : (count[num] = 1)
        })
    
        const res = []
        // 每层节点值选择只能在[1,2]中选择，因此需要nums去重，但是树的层级依旧要是nums.length层，因此还是要传原始长度
        dfs([...new Set(nums)], nums.length, count, 0, [], res)
    
        return res
    };
    
    function dfs(nums, length,  count, level, path, res){
        if(level === length) {
            return res.push([...path]);
        }
    
        for(let i=0; i<nums.length; i++) {
            let num = nums[i]
            
            // 候选节点筛选条件变为：重复元素已经被消耗完了吗
            if(count[num] > 0) {
                path.push(num)
                count[num]--
                dfs(nums, length, count, level+1, path, res)
                count[num]++
                path.pop()
            }
        }
    }

![f2fa8d40632a4d668bb0cc4ed6dd17a9.png][]

[47. _ II - _LeetCode]: https://leetcode.cn/problems/permutations-ii/
[60333fdfc9cd4bba9683285bf93694c4.png]: https://img-blog.csdnimg.cn/60333fdfc9cd4bba9683285bf93694c4.png
[f2fa8d40632a4d668bb0cc4ed6dd17a9.png]: https://img-blog.csdnimg.cn/f2fa8d40632a4d668bb0cc4ed6dd17a9.png