LeetCode-47. 全排列 II

青旅半醒 2024-03-26 02:25 49阅读 0赞

#### 目录 ####

*   *  题目思路
     *  回溯法
     *  拓展

题目来源  
[47. 全排列 II][47. _ II]

### 题目思路 ###

这道题目和46.全排列的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列。  
**强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。**  
我以示例中的 \[1,1,2\]为例  
![在这里插入图片描述][df9c4e0c1b2a4cf5a3278f4271402b80.png]  
图中我们对同一树层，前一位（也就是nums\[i-1\]）如果使用过，那么就进行去重。  
**一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。**

### 回溯法 ###

class Solution {
        
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] used;
        public List<List<Integer>> permuteUnique(int[] nums) {
        
            if(nums == null || nums.length < 1){
        
                return result;
            }
            used = new boolean[nums.length];
            Arrays.sort(nums);
            backTracking(nums,used);
            return result;
        }
    
        public void backTracking(int[] nums,boolean[] used){
        
            if(path.size() == nums.length){
        
                result.add(new ArrayList(path));
                return;
            }
            for(int i =0;i<nums.length;i++){
        
                if(i>0&&nums[i] == nums[i-1] && used[i-1]==false){
        
                    continue;
                }
                if(used[i]){
        
                    continue;
                }
                used[i] = true;
                path.add(nums[i]);
                backTracking(nums,used);
                used[i] = false;
                path.remove(path.size()-1);
            }
        }
    }

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

### 拓展 ###

去重最为关键的代码为：

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)，的树形结构如下：  
![在这里插入图片描述][58ca65d9afa440419b639e15705ba6bb.png]  
树枝上去重（used\[i - 1\] == true）的树型结构如下：  
![在这里插入图片描述][5832e9b4e3a24ad5919324721f2c45c5.png]  
树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

[47. _ II]: https://leetcode.cn/problems/permutations-ii/
[df9c4e0c1b2a4cf5a3278f4271402b80.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c10650041d1844298292c15045cd7e60.png
[7432335fe8354dcaa2f62f71ad17b65a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ab791ed6d25f4cd284d70af25006b98d.png
[58ca65d9afa440419b639e15705ba6bb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/5e091f3b979647a9ba47265e539d276d.png
[5832e9b4e3a24ad5919324721f2c45c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/fea54bd0dbde475cbc61134e9c2931c1.png