47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: 

1
[1,1,2]

输出:

1
2
3
4
5
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Solution1(set去重)：

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
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> tmp;
    vector<bool> bt;
    int n;
    set<vector<int>> s;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        bt = vector<bool>(n);
        sort(nums.begin(),nums.end());
        dfs(0,0,nums);
        return ans;
    }
    void dfs(int u,int start,vector<int> &nums){
        if(u == n){
            if(!s.count(tmp)){
            ans.push_back(tmp);
                s.insert(tmp);
            }
            return;
        }
        for(int i = 0; i < n; i++){
            if(!bt[i]){
                bt[i] = true;
                tmp.push_back(nums[i]);
                dfs(u+1,start,nums);
                tmp.pop_back();
                bt[i] = false;
            }
        }
    }
};

思路：

去重问题，首先想到set，比较简单粗暴的都放到set容器里，有重复就不往答案里面去。

Solution2（排序去重）：

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
41
class Solution {
    
public:
    vector<vector<int>> ans;
    vector<int> tmp;
    vector<bool> bt;
    int n;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        bt = vector<bool>(n);
        sort(nums.begin(),nums.end());
        dfs(0,0,nums);
        return ans;
    }
    bool judge(int i,vector<int> nums){
        for(int j = 0; j < i; j++){
            if(nums[i] == nums[j]){
                if(!bt[j]) return false;
            }
        }
        return true;
    }
    
    void dfs(int u,int start,vector<int> &nums){
        if(u == n){
            ans.push_back(tmp);
            return;
        }
        for(int i = 0; i < n; i++){
            //如果所选是重复数，并且前面都选过了，才能选择当前的。
            if(!bt[i] && (i == 0 ? 1 : nums[i-1] == nums[i] ? bt[i-1] : 1)){
                bt[i] = true;
                tmp.push_back(nums[i]);
                dfs(u+1,start,nums);
                tmp.pop_back();
                bt[i] = false;
            }
            
        }
    }
};

思路：

选择不重复元素的全排列我们已经解决过了，现在我们研究如何去重的问题。

首先我们发现去重的原因是两个位置不同的相同的数在交换之后，整体排列不变，这样就会产生重复，为了达到去重的目的，我们人为规定，当前元素必须在所有在它之前的元素都已经被选了以后，它才能选。这样，相同元素的相对位置就固定下来，不会发生交换重复问题。所以为了方便，我们把相同的元素排在一起，这时需要先排序。