সমস্যা
একটি পজিটিভ ইন্টিজার `n` দেওয়া আছে। `n`-কে পজিটিভ ইন্টিজারগুলোর যোগফল হিসেবে লেখার সব সম্ভাব্য ইউনিক উপায় (পার্টিশন) প্রিন্ট করুন। অর্ডার বিবেচনা করা হয় না (যেমন 2+1 এবং 1+2 একই)।
এলগরিদম
ব্যাকট্র্যাকিং / রিকার্শন ব্যবহার করে সব পার্টিশন জেনারেট করা হয়। একটি অ্যারে `p` রাখা হয় বর্তমান পার্টিশনের জন্য। প্রতিটি ধাপে সবচেয়ে ডানে থাকা নন-১ ভ্যালু খুঁজে বের করা হয়, তা ডিক্রিমেন্ট করা হয়, এবং বাকি ভ্যালুটাকে নতুন পার্টিশনে বিতরণ করা হয়।
উদাহরণ কোড
#include <iostream>
#include <vector>
using namespace std;
void printPartition(vector<int>& p, int len) {
for (int i = 0; i < len; i++)
cout << p[i] << " ";
cout << "\n";
}
void generatePartitions(int n) {
vector<int> p(n); // Max size n (all 1s)
int k = 0; // Last index
p[k] = n; // First partition = n itself
while (true) {
printPartition(p, k + 1);
// Find rightmost non-1 value
int rem_val = 0;
while (k >= 0 && p[k] == 1) {
rem_val += p[k];
k--;
}
if (k < 0) return; // All 1s, done
p[k]--; // Decrease it
rem_val++; // Add 1 to remainder
// Distribute remainder in parts of size p[k]
while (rem_val > p[k]) {
p[k + 1] = p[k];
rem_val -= p[k];
k++;
}
p[k + 1] = rem_val;
k++;
}
}
int main() {
cout << "ইনপুট নম্বর: ";
int n; cin >> n;
cout << n << "-র সব ইউনিক পার্টিশন:\n";
generatePartitions(n);
return 0;
}আউটপুট উদাহরণ
ইনপুট: 5 আউটপুট: 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1
ব্যাখ্যা
এই অ্যালগরিদমটি লেক্সিকোগ্রাফিক অর্ডারে পার্টিশন জেনারেট করে। এটি ইন্টিজার পার্টিশন সমস্যার একটি ক্লাসিক ইটারেটিভ সমাধান। টাইম কমপ্লেক্সিটি পার্টিশন সংখ্যার অনুপাতিক (প্রায় O(n × p(n))), যেখানে p(n) হলো পার্টিশন ফাংশন।
