LeetCode47：全排列②

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

解题思想
因为存在去重操作，因此要注重树层上的去重操作
全排列的树层去重操作

 if(i>0 && nums[i] ==nums[i-1] &&used[i-1]==false) //树层去重
      continue;
1
2

组合的树层去重操作

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

或

 if (i > startIndex && candidates[i] == candidates[i - 1]) 
      continue;
1
2

代码

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backTracking(vector<int>& nums, vector<bool>used) {
        if(path.size()==nums.size()){
                res.push_back(path);
                return;
        }

        for(int i=0;i<nums.size();i++){
            if(i>0 && nums[i] ==nums[i-1] &&used[i-1]==false) //树层去重
                continue;
            
            if(used[i]==true) continue; //在树枝上避免重复使用

            used[i]=true;
            path.push_back(nums[i]);
            backTracking(nums,used);
            used[i]=false;
            path.pop_back();

        }
    
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        backTracking(nums, used);
        return res;
        
    }
};
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