একটি পজিটিভ ইন্টিজার n দেওয়া থাকলে আমাদের {1, 2, 3, 4,… n} সেটের সব সাবসেট প্রিন্ট করতে হবে কোনো অ্যারে বা লুপ ব্যবহার ছাড়া।
যেমন আমাদের ৩ দেওয়া থাকলে সেট {1, 2, 3}-এর সব সাবসেট প্রিন্ট করতে হবে যেগুলো হলো {1 2 3}, {1 2}, {2 3}, {1 3}, {1}, {2}, {3} { }।
কিন্তু আমাদের এটি কোনো লুপ বা অ্যারে ছাড়া করতে হবে। তাই শুধু রিকার্শনই এই ধরণের সমস্যা অ্যারে বা লুপ ছাড়া সমাধান করার একমাত্র উপায়।
উদাহরণ
ইনপুট: 3 আউটপুট: { 1 2 3 }{ 1 2 }{ 1 3 }{ 1 }{ 2 3 }{ 2 }{ 3 }{ }
ব্যাখ্যা: সেট হবে {1 2 3} য থেকে সাবসেটগুলো বের করব
ইনপুট: 4 আউটপুট: { 1 2 3 4 }{ 1 2 3 }{ 1 2 4 }{ 1 2 }{ 1 3 4 }{ 1 3 }{ 1 4 }{ 1 }{ 2 3 4 }{ 2 3 }{ 2 4 }{ 2 }{ 3 4 }{ 3 }{ 4 }{ }
দেওয়া সমস্যা সমাধানের জন্য আমরা যে পদ্ধতি ব্যবহার করব −
- num = 2^n -1 থেকে ০ পর্যন্ত শুরু করুন।
- n সংখ্যক বিট সহ num-এর বাইনারি রিপ্রেজেন্টেশন বিবেচনা করুন।
- বামপাশের বিট থেকে শুরু করুন যা ১ রিপ্রেজেন্ট করে, দ্বিতীয় বিট ২ রিপ্রেজেন্ট করে এবং এভাবেই nth বিট n রিপ্রেজেন্ট করে।
- যদি বিট সেট থাকে তবে সংশ্লিষ্ট নম্বর প্রিন্ট করুন।
- উপরোক্ত ধাপগুলো num ০ হওয়া পর্যন্ত সব মানের জন্য দুहरান।
উপযুক্ত পদ্ধতিটি বিস্তারিত বুঝি একটি সহজ উদাহরণ দিয়ে −
ইনপুট n = 3 মনে করলে, সমস্যা শুরু হয় num = 2^3 - 1 = 7 থেকে
- ৭-এর বাইনারি রিপ্রেজেন্টেশন ⇒ ১ ১ ১
- সংশ্লিষ্ট সাবসেট ⇒ ১ ২ ৩
num থেকে ১ বিয়োগ করলে; num = 6
- ৬-এর বাইনারি রিপ্রেজেন্টেশন ⇒ ১ ১ ০
- সংশ্লিষ্ট সাবসেট ⇒ ১ ২
num থেকে ১ বিয়োগ করলে; num = 5
- ৫-এর বাইনারি রিপ্রেজেন্টেশন ⇒ ১ ০ ১
- সংশ্লিষ্ট সাবসেট ⇒ ১ ৩
num থেকে ১ বিয়োগ করলে; num = 4
- ৪-এর বাইনারি রিপ্রেজেন্টেশন ⇒ ১ ০ ০
- সংশ্লিষ্ট সাবসেট ⇒ ১
এভাবে num = 0 হওয়া পর্যন্ত ইটারেট করলে সব সাবসেট প্রিন্ট হবে।
অ্যালগরিদম
Start
ধাপ ১ → function int subset(int bitn, int num, int num_of_bits) এ
If bitn >= 0
If (num & (1 << bitn)) != 0
Print num_of_bits - bitn
subset(bitn - 1, num, num_of_bits);
Else
Return 0
Return 1
ধাপ ২ → function int printSubSets(int num_of_bits, int num) এ
If (num >= 0)
Print "{ "
subset(num_of_bits - 1, num, num_of_bits) ফাংশন কল
Print "}"
printSubSets(num_of_bits, num - 1) ফাংশন কল
Else
Return 0
Return 1
ধাপ ৩ → function int main() এ
int n = 4 ডিক্লেয়ার ও ইনিশিয়ালাইজ
printSubSets(n, (int) (pow(2, n)) -1) ফাংশন কল
Stop
উদাহরণ
#include <stdio.h>
#include <math.h>
// এই ফাংশন রিকার্সিভলি প্রিন্ট করে
// num-এর বাইনারি রিপ্রেজেন্টেশনের
// সাথে মিলে যাওয়া সাবসেট।
int subset(int bitn, int num, int num_of_bits) {
if (bitn >= 0) {
// প্রদত্ত সাবসেটে নম্বর প্রিন্ট করুন শুধু
// যদি এর সাথে মিলে যাওয়া বিট
// num-এ সেট থাকে।
if ((num & (1 << bitn)) != 0) {
printf("%d ", num_of_bits - bitn);
}
// পরের বিট চেক করুন
subset(bitn - 1, num, num_of_bits);
}
else
return 0;
return 1;
}
// সাবসেট প্রিন্ট করার ফাংশন
int printSubSets(int num_of_bits, int num) {
if (num >= 0) {
printf("{ ");
// num-এর বাইনারি রিপ্রেজেন্টেশনের সাথে
// মিলে যাওয়া সাবসেট প্রিন্ট করুন।
subset(num_of_bits - 1, num, num_of_bits);
printf("}");
// রিকার্সিভলি ফাংশন কল করে
// পরবর্তী সাবসেট প্রিন্ট করুন।
printSubSets(num_of_bits, num - 1);
}
else
return 0;
return 1;
}
// main প্রোগ্রাম
int main() {
int n = 4;
printSubSets(n, (int) (pow(2, n)) -1);
}
আউটপুট
{ 1 2 3 4 }{ 1 2 3 }{ 1 2 4 }{ 1 2 }{ 1 3 4 }{ 1 3 }{ 1 4 }{ 1 }{ 2 3 4 }{ 2 3 }{ 2 4 }{ 2 }{ 3 4 }{ 3 }{ 4 }{ } 