C++ में क्रमचय II (Permutations II)

मान लीजिए हमारे पास विशिष्ट पूर्णांकों का एक संग्रह है; हमें सभी संभावित क्रमचय ढूंढने हैं। अब यदि सरणी डुप्लिकेट तत्वों को संग्रहीत करती है, तो उस स्थिति को अनदेखा करें जो समान दिख रही हो। यदि सरणी [1,1,3] है, तो परिणाम [[1,1,3], [1,3,1], [3,1,1]] होगा।

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• हम रिकर्सिव दृष्टिकोण का उपयोग करेंगे, यह लिस्ट और इंडेक्स बनाएगा। इंडेक्स प्रारंभ में 0 है
• यदि इंडेक्स = लिस्ट का आकार, तो लिस्ट को res सरणी में डालें, और वापस करें
• i को इंडेक्स से दी गई लिस्ट की लंबाई – 1 तक की रेंज में:
  • यदि लिस्ट[i] = लिस्ट[इंडेक्स] और i इंडेक्स के समान नहीं है, तो अगले चरण को देखे बिना कंटिन्यू करें
  • लिस्ट में इंडेक्स स्टार्ट और i पर मौजूद तत्वों को स्वैप करें
  • permutation(लिस्ट, स्टार्ट + 1)
• प्रारंभ में permutation(लिस्ट) कॉल करें, और res वापस करें

उदाहरण (C++)

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int> > v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << "[";
        for(int j = 0; j < v[i].size(); j++){
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector < vector <int> > res;
    void solve(vector <int> nums, int idx = 0){
        if(idx == nums.size()){
            res.push_back(nums);
            return;
        }
        for(int i = idx; i < nums.size(); i++){
            if(nums[i] == nums[idx] && i != idx) continue;
            swap(nums[i], nums[idx]);
            solve(nums, idx + 1);
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        res.clear();
        sort(nums.begin(), nums.end());
        solve(nums);
        return res;
    }
};

int main(){
    Solution ob;
    vector<int> v = {1,1,3};
    print_vector(ob.permuteUnique(v));
}

इनपुट

[1,1,3]

आउटपुट

[[1,1,3],[1,3,1],[3,1,1]]