Математика задачи 47 перестановок литкода II

Question

Скажите, пожалуйста, почему выражение i>0 && nums[i] == nums[i-1] && !used[i-1] работает над получением уникальных перестановок.И какая математика стоит за этим?
Проблема заключается в следующем:
Учитывая набор чисел, которые могут содержать дубликаты, верните все возможные уникальные перестановки.Пример:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Вот код:

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {   
        vector<vector<int>> result; 
        vector<int> temp;
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtrack(nums, temp, result, used);
        return result;        
    }
    
    void backtrack(vector<int>& nums, vector<int>& temp, vector<vector<int>>& result, vector<bool>& used){
        
        if(temp.size() == nums.size()){
            result.emplace_back(temp);
        }else{
            
            for(int i=0; i<nums.size(); i++){
                if(used[i] || i>0 && nums[i] == nums[i-1] && !used[i-1]) continue; 
                used[i] = true;
                temp.push_back(nums[i]);
                backtrack(nums, temp, result, used);
                used[i] = false;
                temp.pop_back();
            }            
        }        
    }    
};

Answer 1

(1) Вы сортируете вектор, поэтому повторяющиеся значения будут присутствовать в векторе последовательно.

(2) Теперь мы подошли к логике этого условия:

• Поскольку вектор может содержать дубликаты, мы должны убедиться, что одна и та же последовательность не повторяется, начиная с того же элемента снова (дубликат).
  • пример :
    • 1,1,2 (начиная с first один) и 1,1,2 (начиная с second один) => оба одинаковы (мы должны убедиться, что этого не произойдет)

Пример:В [1, 1, 2]

• Если первый элемент последовательности выбран равным 1, то мы должны убедиться, что не собираемся создавать другую последовательность, начинающуюся с другой 1 (дубликат элемента).

• Для этого нам нужно пропустить цикл для всех последовательных повторяющихся элементов.

• В вашем случае после создания последовательности, начиная с первой 1, при втором входе в цикл мы проверяем, является ли текущий элемент дубликатом. nums[i] == nums[i - 1] (этого достаточно, поскольку вы уже отсортировали вектор) и является ли текущий элемент первым элементом последовательности. !used[i - 1].

  • В вашем случае из-за этого условия второй не может быть первым элементом последовательности.