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

与无重复项数字的全排列相似

只需要在每一层执行时，用哈希表判断是否已经遍历过某个数字。如果已经遍历过则剪掉该分支即可。

如图：

#include <unordered_map>
#include <vector>
using namespace std;

/* code here */

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int>> res;
        vector<bool> foot(num.size(), false);
        vector<int> arr;
        quick_sort(num, 0, num.size() - 1);
        recursion(res, num, arr, foot, 0);
        return res;
    }
    
    void recursion(vector<vector<int>> &res, vector<int> &num, vector<int> &arr, vector<bool> &foot, int depth) {
        if (depth == num.size()) {
            res.emplace_back(arr);
            return ;
        }
        unordered_map<int, int> umap;
        for (int i = 0; i < num.size(); ++i) { 
            if (foot[i]) continue;    
            foot[i] = true;
            arr.emplace_back(num[i]);
            if (umap.find(num[i]) == umap.end()) {
                umap[num[i]] = 1;
                recursion(res, num, arr, foot, depth + 1);
            }

            arr.pop_back();
            foot[i] = false;
            
        }
    }
    
    void quick_sort(vector<int> &num, int l, int r) {
        if (l >= r) return ;
        int i = l - 1, j = r + 1;
        int mid = num[(l + r) >> 1];
        while (i < j) {
            do ++i; while (num[i] < mid);
            do --j; while (num[j] > mid);
            if (i < j) swap(num[i], num[j]);
        }
        quick_sort(num, l, j);
        quick_sort(num, j + 1, r);
    }
};