题解 | #有重复项数字的全排列#

思路：由于要升序排列，可以先对原数组进行升序排序。由于此题的数组长度不长，用冒泡排序就行。然后用递归列举出全排列，其中针对相同数字可以用一个map记录下出现过的数字，并且要在每一层递归中用一个新的map去记录。若出现过，就跳过此数字。

#include <unordered_map>
#include <vector>
class Solution {
  public:
    vector<vector<int> > permuteUnique(vector<int>& num) {
        sort(num);
        return permute(num);
    }

    void sort(vector<int>& num) { //冒泡排序
        int tmp;
        for (int j = 0; j < num.size() - 1; j++) {
            for (int i = 0; i < num.size() - j - 1; i++) {
                if (num[i] > num[i + 1]) {
                    tmp = num[i];
                    num[i] = num[i + 1];
                    num[i + 1] = tmp;
                }
            }
        }
    }

    vector<vector<int> > permute(vector<int>& num) {
        vector<vector<int>> res;
        vector<int> tmpnum;
        if (num.size() == 1) {
            tmpnum.push_back(num[0]);
            res.push_back(tmpnum);
            return res;
        }
        vector<vector<int>> tmpres;
        unordered_map<int, bool> hash; // 记录数字是否出现过
        for (int i = 0; i < num.size(); i++) {
            if (hash[num[i]]) {
                continue;
            } else {
                hash[num[i]] = true;
            }
            tmpnum = num;
            tmpnum.erase(tmpnum.begin() + i);
            tmpres = permute(tmpnum);
            for (int j = 0; j < tmpres.size(); j++) {
                tmpres[j].insert(tmpres[j].begin(), num[i]);
                res.push_back(tmpres[j]);
            }
        }
        return res;
    }
};