C++ में फैक्टर कॉम्बिनेशन - संख्या के सभी गुणनखंड संयोजन

समस्या विवरण

मान लीजिए हमारे पास एक संख्या है। संख्याओं को इसके गुणनखंडों के गुणनफल के रूप में माना जा सकता है। जैसे, 8 = 2 x 2 x 2; = 2 x 4। हमें एक फ़ंक्शन बनाना है जो एक पूर्णांक n लेता है और इसके गुणनखंडों के सभी संभावित संयोजन लौटाता है।

उदाहरण के लिए, यदि इनपुट 12 है, तो आउटपुट [[2, 6], [2, 2, 3], [3, 4]] होगा।

समाधान दृष्टिकोण

बैकट्रैकिंग के साथ पुनरावर्ती गुणनखंड विघटन:

1. solve() फ़ंक्शन परिभाषित करें जो n, target, start लेता है:
   • सूचियों की सूची ret परिभाषित करें
   • यदि n == 1, तो ret लौटाएं
   • यदि n != target, तो n को ret में जोड़ें
   • i को start से sqrt(n) तक लूप करें:
     • यदि n % i == 0:
       • other = solve(n/i, target, i)
       • other के प्रत्येक संयोजन के लिए:
         • i को संयोजन के अंत में जोड़ें
         • संयोजन को ret में जोड़ें
   • ret लौटाएं
2. मुख्य विधि से: solve(n, n, 2) लौटाएं

C++ कार्यान्वयन

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

void print_vector(vector<vector<auto> > 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> > solve(int n, int target, int start){ 
        vector < vector <int> > ret; 
        if(n == 1){ 
            return ret; 
        } 
        if(n != target){ 
            ret.push_back({n}); 
        } 
        for(int i = start; i * i <= n; i++){ 
            if(n % i == 0){ 
                vector < vector <int> > other = solve(n / i, target,i); 
                for(int j = 0; j < other.size(); j++){ 
                    other[j].push_back(i); 
                    ret.push_back(other[j]); 
                } 
            } 
        } 
        return ret; 
    } 
    
    vector<vector<int>> getFactors(int n) { 
        return solve(n, n, 2); 
    } 
}; 

int main(){ 
    Solution ob; 
    print_vector(ob.getFactors(16)); 
    return 0;
}

इनपुट

16

आउटपुट

[[8, 2, ],[4, 2, 2, ],[2, 2, 2, 2, ],[4, 4, ],]