Matemáticas detrás del problema leetcode 47 permutaciones II

Question

Por favor dime por qué la expresión i>0 && nums[i] == nums[i-1] && !used[i-1] trabaja para obtener permutaciones únicas.¿Y cuál es la matemática detrás de esto?
El problema es el siguiente:
Dada una colección de números que pueden contener duplicados, devuelve todas las permutaciones únicas posibles.Ejemplo:

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

Aquí está el código:

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) Está ordenando el vector para que los valores duplicados estén presentes consecutivamente en el vector.

(2) Ahora llegamos a la lógica detrás de esa condición:

• Como el vector puede contener duplicados, debemos asegurarnos de no repetir la misma secuencia comenzando con el mismo elemento nuevamente (duplicar)
  • ejemplo :
    • 1,1,2 (empezando con first uno) y 1,1,2 (comenzando con second uno) => ambos son iguales (debemos asegurarnos de que esto no suceda)

Ejemplo:En [1, 1, 2]

• Si el primer elemento de la secuencia se elige como 1, entonces debemos asegurarnos de no crear otra secuencia comenzando con otro 1 (duplicado del elemento).

• Entonces, para eso, debemos omitir el ciclo de todos los elementos duplicados consecutivos.

• En su caso, después de crear una secuencia comenzando con el primer 1, cuando ingresamos al bucle por segunda vez verificamos si el elemento actual es un duplicado. nums[i] == nums[i - 1] (esto es suficiente ya que ya ha ordenado el vector) y si el elemento actual es el primer elemento de la secuencia !used[i - 1].

  • En su caso, debido a esta condición, el segundo no puede ser el primer elemento de la secuencia.