A matemática por trás leetcode problema 47 permutações II

Question

Por favor, diga-me por que a expressão i>0 && nums[i] == nums[i-1] && !used[i-1] funciona em ficar sem igual, permutações.E o que é a matemática por trás disso?
O problema é o seguinte:
Dado um conjunto de números que podem conter duplicatas, retornar todos os únicos possíveis permutações.Exemplo:

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

Aqui está o 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) Você está classificando o vetor de forma que os valores duplicados serão consecutivamente presente no vetor.

(2) Agora vamos para a lógica por trás dessa condição:

• Como o vetor pode conter as duplicatas nós deve se certificar de não repetir a mesma seqüência, iniciando com o mesmo elemento de novo(duplicado)
  • exemplo :
    • 1,1,2 (a começar first um) e 1,1,2 (começando com second um) => ambos são os mesmos (nós deve se certificar de que isso não aconteça)

Exemplo:No [1, 1, 2]

• Se o primeiro elemento da seqüência é escolhido como 1, devemos, então, certifique-se de que nós não vamos criar outra sequência que começa com mais de 1 (duplicata de um elemento).

• Então, para isso, precisamos ignorar o loop para todos os consecutivos elementos duplicados.

• No seu caso, depois de criar uma sequência de olhar com 1, quando entramos no ciclo para o segundo tempo, vamos verificar se o elemento atual é um duplicado nums[i] == nums[i - 1] (isso é suficiente, como você já ordenada do vetor) e se o elemento atual é o primeiro elemento da seqüência !used[i - 1].

  • No seu caso, devido a essa condição, o segundo não pode ser o primeiro elemento da seqüência.