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

回溯不好理解，全排列也乱

class Solution {
  public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
      std::vector<std::vector<int>> res;
      std::vector<int> visited(num.size(), 0);
      std::sort(num.begin(), num.end());
      dfs(res, num, visited, std::vector<int>());
      return res;
    }
  private:
    void dfs(std::vector<std::vector<int>> &res, std::vector<int> &num, std::vector<int> &visited, std::vector<int> tmp) {
      if (tmp.size() == num.size()) {
        res.push_back(tmp);
        return ;
      }
      
      for (int i = 0; i < num.size(); ++i) {
        if (visited[i]) {
          continue;
        }
        //  回溯过程遇到相同数字，不用再排
        if (i > 0 && num[i] == num[i - 1] && !visited[i - 1]) {
          continue;
        }
        visited[i] = 1;
        tmp.push_back(num[i]);
        dfs(res, num, visited, tmp);
        tmp.pop_back();
        visited[i] = 0;
      }
    }
};