Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

跟PermutionsI类似，不过需要去重。

思路是先对原数组排序，然后在循环开始时，跳过重复元素。

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int>> re;
        vector<int> thisRe;
        sort(num.begin(), num.end());
        DFS(num, re, thisRe);
        return re;
    }
    void DFS(vector<int> &num, vector<vector<int>> &re, vector<int> &thisRe){
        if(num.size() == 0) {
            re.push_back(thisRe);
            return ;
        }
        int len = num.size();
        int i = 0;
        while(i < len){
            int tmp = num[i];
            thisRe.push_back(tmp);
            num.erase(num.begin() + i);
            DFS(num, re, thisRe);
            num.insert(num.begin() + i, tmp);
            thisRe.pop_back();
            i++;
            while(i < len && num[i] == num[i - 1]) i++;
        }
    }
};