leeetcode問題の背後にある数学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 Oneから始まる）と1,1,2（second Oneから始まる）=>同じです（これが発生しないことを確認する必要があります）

例：[1, 1, 2]

で

• シーケンス内の最初の要素が1として選択されている場合、私たちは別のシーケンスを別の1（要素の重複）で作成しないことを確認してください。

• それで、私たちはすべての連続した重複要素のループをスキップする必要があります。

• 最初の1で演奏を行った後、1回目のループを入力した後、現在の要素が重複するnums[i] == nums[i - 1]であるかどうかを確認します（これはすでにベクトルをソートしている限りです）。現在の要素がシーケンス!used[i - 1]の最初の要素であるかどうか。

  • あなたの場合、この状態のために、2番目のものはシーケンスの最初の要素にすることはできません。