الرياضيات وراء مشكلة leetcode 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) أنت تقوم بفرز المتجه بحيث تكون القيم المكررة موجودة على التوالي في المتجه.

(٢) نأتي الآن إلى المنطق وراء هذا الشرط:

• نظرًا لأن المتجه يمكن أن يحتوي على التكرارات، فيجب علينا التأكد من عدم تكرار نفس التسلسل من خلال البدء بنفس العنصر مرة أخرى (مكرر)
  • مثال :
    • 1,1,2 (بدءا من first واحد) و1،1،2 (يبدأ بـ second واحد) => كلاهما متماثلان (يجب أن نتأكد من عدم حدوث ذلك)

مثال:في [1, 1, 2]

• إذا تم اختيار العنصر الأول في التسلسل كـ 1، فيجب علينا التأكد من أننا لن نقوم بإنشاء تسلسل آخر يبدأ بـ 1 آخر (نسخة مكررة من العنصر).

• لذلك، نحتاج إلى تخطي الحلقة لجميع العناصر المكررة المتتالية.

• في حالتك، بعد إنشاء تسلسل يبدأ بالرقم 1 الأول، عندما ندخل الحلقة للمرة الثانية، نتحقق مما إذا كان العنصر الحالي مكررًا nums[i] == nums[i - 1] (وهذا يكفي لأنك قمت بالفعل بفرز المتجه) وما إذا كان العنصر الحالي هو العنصر الأول في التسلسل !used[i - 1].

  • في حالتك، وبسبب هذا الشرط، لا يمكن أن يكون العنصر الثاني هو العنصر الأول في التسلسل.