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

class Solution {
  public:
    void recursion(vector<int>& num, vector<vector<int>>& ans, vector<int>& vis, vector<int>& tmp) {
        if (tmp.size() == num.size()) { // 已得到一个结果
            ans.push_back(tmp);
            return;
        }
        // 遍历所有元素 选取加入
        for(int i=0; i<num.size(); ++i)
        {
            if(vis[i]) continue; // 若该元素被加入 标记过 就跳过

            if(i>0 && num[i] == num[i-1] && vis[i-1]) // 注意这里的标记数组 两种都对 !vis[i-1]
            {
                // 和上个元素相同 且上一个已经使用过 跳过
                continue;
            }

            vis[i] = 1; // 标记
            tmp.push_back(num[i]);
            // 进入下一层
            recursion(num, ans, vis, tmp);
            // 回溯
            vis[i] = 0;
            tmp.pop_back();
        }
 
    }

    vector<vector<int> > permuteUnique(vector<int>& num) {

        int n = num.size();
        // 标记数组
        vector<int> vis(n, 0);
        sort(num.begin(), num.end());
        vector<vector<int>> ans;
        vector<int> tmp; // 用于存储每个可能排序的数组
        // 递归函数 
        recursion(num, ans, vis, tmp);
        return ans;

    }
};

使用标记数组