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

class Solution {
  public:
    vector<vector<int>> permuteUnique(vector<int>& num) {
        vector<vector<int>> result;
        vector<int> path;
        vector<bool> used(num.size(), false); // 标记元素是否被使用过

        sort(num.begin(), num.end());
        backtrack(num, used, path, result);
        return result;
    }

  private:
    void backtrack(vector<int>& num, vector<bool>& used, vector<int>& path,
                   vector<vector<int>>& result) {
        // 当路径长度等于数组长度时，说明找到一个排列
        if (path.size() == num.size()) {
            result.push_back(path);
            return;
        }

        // 遍历所有可能的选项
        for (int i = 0; i < num.size(); i++) {
            // 如果当前数字已经被使用过，跳过
            if (used[i]) {
                continue;
            }
            // 关键去重逻辑：如果当前数字与前一个数字相同，且前一个数字未被使用，则跳过
            // 这样可以确保相同的数字按照顺序被使用，避免重复排列
            if (i > 0 && num[i] == num[i - 1] && !used[i - 1]) {
                continue;
            }

            // 做选择
            used[i] = true;
            path.push_back(num[i]);

            // 递归进入下一层决策树
            backtrack(num, used, path, result);

            // 撤销选择（回溯）
            path.pop_back();
            used[i] = false;
        }
    }
};

只用在无重复数字的全排列上加上一个去重逻辑
核心思想
这个去重逻辑的关键在于：对于相同的数字，我们强制要求它们必须按照在数组中的原始顺序被使用。
如果前一个数字没用过,就跳过,因为只有在前面的数字使用过后才能使用当前数字;
如果前面的数字使用过了,当前的数字才可以使用