47.全排列 II

男娘i 2023-10-16 14:09 20阅读 0赞

#### 47.全排列 II ####

*  题干描述
 *  解题思路
 *  拓展
 *  总结
 *  代码实现

## 题干描述 ##

[力扣入口][Link 1]

给定一个可包含重复数字的序列 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

## 解题思路 ##

这道题目和**46.全排列**的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列。

这里又涉及到去重了。

在**40.组合总和II**、**90.子集II**我们分别详细讲解了组合问题和子集问题如何去重。

那么排列问题其实也是一样的套路。

**还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了**。

我以示例中的 \[1,1,2\]为例 （为了方便举例，已经排序）抽象为一棵树，去重过程如图：  
![在这里插入图片描述][edb3a00314f24b50ab4b2873a1fd9bc4.png]  
图中我们对同一树层，前一位（也就是nums\[i-1\]）如果使用过，那么就进行去重。

**一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果**。

在**46.全排列**中已经详细讲解了排列问题的写法，在**40.组合总和II**、**90.子集II**中详细讲解了去重的写法，所以这次我就不用回溯三部曲分析了。

## 拓展 ##

去重最为关键的代码为：

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
        
        continue;
    }

**如果改成 used\[i - 1\] == true， 也是正确的!**，去重代码如下：

if(i > 0 && nums[i] == nums[i - 1] && used[i -  1] == true){
        
    	continue;
    }

这是为什么呢，就是上面我刚说的，如果要对树层中前一位去重，就用`used[i - 1] == false`，如果要对树枝前一位去重用`used[i - 1] == true`。

**对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高!**

这么说是不是有点抽象？

来来来，我就用输入: \[1,1,1\] 来举一个例子。

树层上去重(used\[i - 1\] == false)，的树形结构如下：  
![在这里插入图片描述][5f690a7a8b0245528091f41456956c2e.png]  
树枝上去重（used\[i - 1\] == true）的树型结构如下：  
![在这里插入图片描述][f79e99d78ed041cf928fbd4771ae8251.png]  
大家应该很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

## 总结 ##

这道题其实还是用了我们之前讲过的去重思路，但有意思的是，去重的代码中，这么写：

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
        
        continue;
    }

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
        
        continue;
    }

都是可以的，这也是很多同学做这道题目困惑的地方，知道`used[i - 1] == false`也行而`used[i - 1] == true`也行，但是就想不明白为啥。

所以我通过举\[1,1,1\]的例子，把这两个去重的逻辑分别抽象成树形结构，大家可以一目了然：为什么两种写法都可以以及哪一种效率更高！

这里可能大家又有疑惑，既然`used[i - 1] == false`也行而`used[i - 1] == true`也行，那为什么还要写这个条件呢？

直接这样写 不就完事了？

if (i > 0 && nums[i] == nums[i - 1]) {
        
        continue;
    }

其实并不行，一定要加上 `used[i - 1] == false`或者`used[i - 1] == true`，因为 used\[i - 1\] 要一直是 true 或者一直是false才可以，而不是一会是true 一会又是false。 所以这个条件要写上。

是不是豁然开朗了！

## 代码实现 ##

class Solution {
        
        // 47.全排列II
        // 存放结果
        List<List<Integer>> result12 = new ArrayList<>();
        // 暂存结果
        List<Integer> path12 = new ArrayList<>();
    
        public List<List<Integer>> permuteUnique(int[] nums){
        
            boolean[] used = new boolean[nums.length];
            Arrays.fill(used, false);
            Arrays.sort(nums);
            backTrack(nums, used);
            return result12;
        }
    
        private void backTrack(int[] nums, boolean[] used){
        
            if(path12.size() == nums.length){
        
                result12.add(new ArrayList<>(path12));
                return;
            }
            for(int i = 0; i < nums.length; i++){
        
                // used[i - 1] == ture, 说明同一树枝nums[i - 1]使用过
                // used[i - 1] == false, 说明同一树层nums[i - 1]使用过
                // 如果同一树层nums[i - 1]使用过则直接跳过
                if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){
        
                    continue;
                }
                // 如果同一树枝nums[i]没使用过开始处理
                if(used[i] == false){
        
                    used[i] = true; // 标记同一树枝nums[i]使用过，防止同一树枝重复使用
                    path12.add(nums[i]);
                    backTrack(nums, used);
                    path12.remove(path12.size() - 1); // 回溯，说明同一树层nums[i]使用过，防止下一树层重复
                    used[i] = false; // 回溯
                }
            }
        }
    }

**参考资料**：[代码随想录-47.全排列 II][-47._ II]

[Link 1]: https://leetcode.cn/problems/permutations-ii/
[edb3a00314f24b50ab4b2873a1fd9bc4.png]: https://img-blog.csdnimg.cn/edb3a00314f24b50ab4b2873a1fd9bc4.png
[5f690a7a8b0245528091f41456956c2e.png]: https://img-blog.csdnimg.cn/5f690a7a8b0245528091f41456956c2e.png
[f79e99d78ed041cf928fbd4771ae8251.png]: https://img-blog.csdnimg.cn/f79e99d78ed041cf928fbd4771ae8251.png
[-47._ II]: https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE