Mathematik hinter Leetcode-Problem 47 Permutationen II

Question

Bitte sagen Sie mir, warum der Ausdruck i>0 && nums[i] == nums[i-1] && !used[i-1] arbeitet daran, eindeutige Permutationen zu erhalten.Und welche Mathematik steckt dahinter?
Das Problem ist wie folgt:
Geben Sie bei einer Sammlung von Zahlen, die möglicherweise Duplikate enthalten, alle möglichen eindeutigen Permutationen zurück.Beispiel:

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

Hier ist der 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) Sie sortieren den Vektor so, dass im Vektor nacheinander doppelte Werte vorhanden sind.

(2) Nun kommen wir zur Logik hinter dieser Bedingung:

• Da der Vektor Duplikate enthalten kann, sollten wir darauf achten, nicht dieselbe Sequenz zu wiederholen, indem wir erneut mit demselben Element beginnen (Duplikat).
  • Beispiel :
    • 1,1,2 (beginnen mit first eins) und 1,1,2 (beginnend mit second eins) => beide sind gleich (wir sollten sicherstellen, dass das nicht passiert)

Beispiel:In [1, 1, 2]

• Wenn das erste Element in der Sequenz als 1 ausgewählt wird, sollten wir sicherstellen, dass wir keine weitere Sequenz erstellen, die mit einer weiteren 1 (Duplikat des Elements) beginnt.

• Dazu müssen wir die Schleife für alle aufeinanderfolgenden doppelten Elemente überspringen.

• In Ihrem Fall überprüfen wir nach dem Erstellen einer Sequenz, die mit der ersten 1 beginnt, beim zweiten Eintritt in die Schleife, ob das aktuelle Element ein Duplikat ist nums[i] == nums[i - 1] (Dies reicht aus, da Sie den Vektor bereits sortiert haben) und ob das aktuelle Element das erste Element der Sequenz ist !used[i - 1].

  • In Ihrem Fall kann aufgrund dieser Bedingung das zweite nicht das erste Element der Sequenz sein.