【leetcode】47 Permutations II

发表于 | 分类于 ，


描述

有重复数字的全排列

样例

样例1

1
2
3
4
5
6
7
输入: 1 1 2
输出:
       [
         [1,1,2],
         [1,2,1],
         [2,1,1]
       ]

思路

回溯，加个index，利用 set ，这样比较慢。
回溯的两种做法，一种是直接往 temp 数组里面放元素，一种是改变 nums 数组，得到全排列也可以通过交换两个数的位置得到，不是吗？

代码

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
92 ms
class Solution {
private:
    void backtrack(vector<int> &nums,set<vector<int>> & result ,vector<int> temp,vector<int> &pos){
        if(temp.size() == nums.size()){
            result.insert(temp);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(find(pos.begin(),pos.end(),i) == pos.end()){
                pos.push_back(i);
                temp.push_back(nums[i]);
                backtrack(nums,result,temp,pos);
                temp.pop_back();
                pos.pop_back();
            }
        }

    }

public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        set<vector<int>> res;
        vector <int> temp;
        vector <int> pos;
        backtrack(nums,res,temp,pos);
        return vector<vector<int>>(res.begin(),res.end());
    }
};

更快一点的做法

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
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        if (nums.size() == 0) {
            return res;
        }
        dfs(nums, res, 0);
        return res;
    }

    void dfs(vector<int>& nums, vector<vector<int>>& res, int index) {
        if (index == nums.size()) {
            res.push_back(nums);
            return;
        }
        unordered_set<int> uset;
        for (int i = index; i < nums.size(); ++i) {
            if (uset.find(nums[i]) == uset.end()) {
                uset.insert(nums[i]);
                swap(nums[i], nums[index]);
                dfs(nums, res, index + 1);
                swap(nums[i], nums[index]);
            }
        }
    }
};

参考

原题链接