C++-এ Factor Combinations: সংখ্যার সব ফ্যাক্টর কম্বিনেশন বের করা

একটি সংখ্যা n দেওয়া আছে। এর সব সম্ভাব্য ফ্যাক্টর কম্বিনেশন (ফ্যাক্টরগুলোর গুণফল = n) বের করতে হবে। নোট: ১ এবং n নিজে ফ্যাক্টর হিসেবে বিবেচনা করা হয় না।

উদাহরণ

ইনপুট: 12

আউটপুট: [[2, 6], [2, 2, 3], [3, 4]]

ব্যাখ্যা: ১২ = ২×৬ = ২×২×৩ = ৩×৪।

সমাধানের পদ্ধতি (Recursive Backtracking)

রিকারসিভ ফাংশন solve(n, target, start):
- target = মূল সংখ্যা (ডুপ্লিকেট এড়াতে), start = ফ্যাক্টর খুঁজতে শুরু করার ন্যূনতম ভ্যালু।
- রেজাল্ট লিস্ট ret।
- যদি n == 1, তবে খালি রিটার্ন (বেস কেস)۔
- যদি n != target (অর্থাৎ মূল কল নয়), তবে n কে একটি কম্বিনেশন হিসেবে ret-এ যোগ করুন।
- i = start থেকে i*i <= n পর্যন্ত লুপ:
  - যদি n % i == 0:
    - other = solve(n/i, target, i) (রিকারসিভ কল, নন-ডিক্রিজিং অর্ডার মেইনটেইন করতে start = i)।
    - প্রতিটি other কম্বিনেশনে i প্রিপেন্ড করে ret-এ যোগ করুন।
- ret রিটার্ন করুন।
মেইন থেকে solve(n, n, 2) কল করুন।

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>> 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;
}

ইনপুট

আউটপুট

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