Les mathématiques derrière leetcode problème 47 permutations II

Question

S'il vous plaît dites-moi pourquoi l'expression i>0 && nums[i] == nums[i-1] && !used[i-1] travaux sur l'obtention d'une unique permutations.Et qu'est-ce que les mathématiques derrière elle?
Le problème est comme suit:
Étant donné un ensemble de chiffres qui pourraient contenir des doublons, de retour possible unique de permutations.Exemple:

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

Voici le code:

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) à trier le vecteur donc les valeurs en double sera consécutivement présent dans le vecteur.

(2) nous en arrivons Maintenant à la logique derrière cette condition:

• Comme le vecteur peut contenir des doublons, nous devons nous assurer de ne pas répéter la même séquence, en commençant par le même élément nouveau(double)
  • exemple :
    • 1,1,2 (en commençant par first l'un) et 1,1,2 (en commençant par second un) => les deux sont les mêmes (nous devons nous assurer que cela n'arrive pas)

Exemple:Dans [1, 1, 2]

• Si le premier élément de la séquence est 1, alors nous devons nous assurer que nous n'allons pas créer une autre séquence, à partir de 1 autre (double de l'élément).

• Donc pour cela, nous avons besoin de passer la boucle pour tous consécutive, les éléments en double.

• Dans votre cas, après la création d'une séquence de regarder avec en premier: 1, quand nous entrons dans la boucle pour la deuxième fois, nous avons vérifier si l'élément courant est un doublon nums[i] == nums[i - 1] (cela est suffisant comme vous l'avez déjà trié le vecteur) et si l'élément courant est le premier élément de la séquence !used[i - 1].

  • Dans votre cas, en raison de cette condition, le second ne peut pas être le premier élément de la séquence.