47.全排列II

发表于： 分类于：
字数： 1248 阅读：≈ 3分钟

😏47.全排列II

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

思路

基本想法

基本思想与无重复元素的全排列一样，都需要每次取出集合中的一个未使用元素，将其标记为已使用，并进行递归，但是本题中是可重复元素，所以需要考虑去重

去重并不是直接将集合中的重复元素去除掉在进行全排列，而是在搜索时，每一层中同样的元素只可以使用一次，但是不同层可以使用值相同的元素

如何理解：例如[1,1,2,2]，第一层取一个1，剩下的集合为[1,2,2]，第二层还是可以取一个1，剩下[2,2]，第三层取2，剩下[2]，第四层取一个2，剩下[]，此时形成一个全排列，达到递归返回的条件，并且for循环也结束，直接退回到第三层，此时剩下元素[2]，但是这个2不能使用，与红色的2值相同，并且处于同一层，这样一直搜索下去，形成一个搜索树：

image-20230525201725618

总结来说，由于元素经过排序，所以在同一层中，出现当前元素与前一个元素重复，并且前一个元素被使用，那么当前元素就不能被使用了

执行流程

主要需要考虑的就是如何去重，与之前子集的去重思路一样，但是增加了一个判断条件，由于之前的子集问题使用startIndex直接缩小集合的大小，进入下一层之前就可以将上一层使用的元素剔除掉，而排列问题不行，所以增加一个判断条件，很巧妙。

增加的条件：flag[i-1]==false，当flag为true时说明纵向遍历中元素被使用过，当flag为false说明横向遍历中元素被使用，为什么。因为同一层元素横向便利时，必然是遇到了回溯，也就是说flag[i]=false,在进行下一个元素的判断，所以此处是flag[i-1]==false

所以去重条件为：

1
2

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

当前元素与上一个元素重复，并且上一个元素被使用过（经过回溯之后标志数组变成false）,那么当前元素不能被使用。

其实flag[i-1]==true也可以作为判断条件，只是不太好理解，这里选择放弃

flag[i-1]==true形成的判断树点这里

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
public:
    //定义全局变量
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        if(nums.size()==0)
            return res;
        vector<bool> flag(nums.size(),false);
        sort(nums.begin(),nums.end());
        backtrack(nums,flag);
        return res;
    }
    void backtrack(vector<int>& nums,vector<bool>& flag){
        if(path.size()==nums.size()){
            res.push_back(path);
            return;
        }
        //横向遍历
        for(int i=0;i<nums.size();++i){
            //判断元素是否被使用或者同一层中已经有相等的元素被使用
            // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false，说明同一树层nums[i - 1]使用过
            // 如果同一树层nums[i - 1]使用过则直接跳过
            if(i>0&&nums[i]==nums[i-1]&&flag[i-1]==false)
                continue;
            //到这里就是当前元素可以被使用
            if(flag[i]==false){
                path.push_back(nums[i]);
                //当前元素被使用
                flag[i]=true;
                //进行纵向遍历
                backtrack(nums,flag);
                //回溯
                path.pop_back();
                flag[i]=false;
            }
        }
    }
};

总结

相比于没有重复元素的全排列，此题只是多了一个去重的逻辑，但是不要小看！！！！

去重的逻辑是lag[i-1]==false，为什么使用false一定要搞清楚