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

class Solution {
public:
    /**
      * 从数组num中挑选一个数放入item中
      * 标记该位置被使用arrIsUser[i] = 1;
      * 在递归从剩余数中选择加入到item
      * 同时set插入该数表示不能再插入同样数字到item当前位置
      * item.size() == num.size() 一组排列
      */
    void dfs(vector<vector<int>> &res, vector<int> &num, vector<int> &item, vector<int> &arrIsUser) {
        if (item.size() == num.size()) {
            res.push_back(item);
            return;
        }
        // 记录当前层已经使用过的数
        set<int> check;
        for(int i = 0; i < num.size(); i++) {
            if (check.find(num[i]) != check.end() || arrIsUser[i]) continue;
            check.insert(num[i]); // 插入
            arrIsUser[i] = 1;
            item.push_back(num[i]);
            dfs(res, num, item, arrIsUser);
            arrIsUser[i] = 0;
            // check.erase(num[i]); // 删除
            item.pop_back();
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(), num.end());
        vector<vector<int>> res;
        vector<int> item;
        vector<int> arrIsUser(num.size(), 0);
        dfs(res, num, item, arrIsUser);
        return res;
    }
};
static const auto io_sync_off = []() { //lambda函数
    // turn off sync，关闭输入输出流的缓存
    std::ios::sync_with_stdio(false);
    // untie in/out streams，实现输入和输出流的解绑
    std::cin.tie(nullptr);
    return nullptr;
}
();