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

整体思路同无重复数组全排列，dfs进行搜索。1.引入flag标记num中各个数是否已被使用，2.dfs遍历搜索中用num_pool缓存已经出现过的num数字，避免res相同位置相同数字的重复遍历。

class Solution {
  public:
    vector<vector<int>> res;
    void dfs(vector<int> num, vector<int>& temp, vector<int>& flag) {
        if (temp.size() == num.size()) {
            res.push_back(temp);
            return ;
        }
        vector<int> num_pool;//缓存此排列位置已经用过的数，以跳过此位置重复数字的后续排列结果
        for (int i = 0; i < num.size(); i++) {
            if (flag[i] ||find(num_pool.begin(), num_pool.end(), num[i]) != num_pool.end()) {
                continue;
            }
            flag[i] = 1;
            num_pool.push_back(num[i]);
            temp.push_back(num[i]);
            dfs(num, temp, flag);
            temp.pop_back();
            flag[i] = 0;
        }
    }

    vector<vector<int> > permuteUnique(vector<int>& num) {
        sort(num.begin(), num.end());
        vector<int> temp;
        vector<int> flag(num.size(), 0); //用于标记num中的数是否被用过
        dfs(num, temp, flag);
        return res;
    }
};