एक धनात्मक पूर्णांक n को देखते हुए हमें {1, 2, 3, 4,… n} के सेट के सभी सबसेट को बिना किसी ऐरे या लूप का उपयोग किए प्रिंट करना होगा।
जैसे हमने कोई संख्या दी है जैसे कि 3 s हमें समुच्चय {1, 2, 3} के सभी उपसमुच्चय को प्रिंट करना है जो {1 2 3}, {1 2}, {2 3}, {1 3} होगा। {1}, {2}, {3} { }.
लेकिन हमें यह बिना किसी लूप या ऐरे का उपयोग किए करना है। इसलिए, किसी सरणी या लूप का उपयोग किए बिना इस प्रकार की समस्या को हल करने के लिए केवल रिकर्सन ही संभव तरीका है।
उदाहरण
Input: 3
Output: { 1 2 3 }{ 1 2 }{ 1 3 }{ 1 }{ 2 3 }{ 2 }{ 3 }{ }
Explanation: The set will be {1 2 3} from which we will find the subsets
Input: 4
Output: { 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 }{ } दृष्टिकोण हम दी गई समस्या को हल करने के लिए उपयोग करेंगे -
- संख्या =2^n -1 से 0 तक प्रारंभ करें।
- संख्या के n संख्या के साथ द्विआधारी प्रतिनिधित्व पर विचार करें।
- सबसे बाएं बिट से प्रारंभ करें जो 1 का प्रतिनिधित्व करता है, दूसरा बिट 2 का प्रतिनिधित्व करता है और इसी तरह nth बिट तक जो n का प्रतिनिधित्व करता है।
- यदि बिट सेट है तो उसके अनुरूप संख्या प्रिंट करें।
- संख्या के सभी मानों के लिए उपरोक्त चरणों का पालन करें जब तक कि यह 0 के बराबर न हो जाए।
आइए बताए गए दृष्टिकोण को विस्तार से समझते हैं कि यह एक साधारण उदाहरण का उपयोग करके कैसे काम करता है -
इनपुट n =3 मानते हुए, इसलिए समस्या num =2^3 - 1 =7 से शुरू होती है
- 7 का बाइनरी प्रतिनिधित्व
| 1 | 1 | 1 |
- संबंधित उपसमुच्चय ⇒
| 1 | 2 | 3 |
संख्या में से 1 घटाना; अंक =6
- 6 का बाइनरी प्रतिनिधित्व
| 1 | 1 | 0 |
- संबंधित उपसमुच्चय ⇒
| 1 | 2 | <टीडी>
संख्या में से 1 घटाना; अंक =5
- 5 का बाइनरी प्रतिनिधित्व
| 1 | 0 | 1 |
- संबंधित उपसमुच्चय ⇒
| 1 | <टीडी>3 |
संख्या में से 1 घटाना; अंक =4
- 4 का बाइनरी प्रतिनिधित्व
| 1 | 0 | 0 |
- संबंधित उपसमुच्चय ⇒
| 1 | <टीडी>
इसी तरह हम num =0 तक पुनरावृति करेंगे और सभी सबसेट को प्रिंट करेंगे।
एल्गोरिदम
Start
Step 1 → In 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
Step 2 → In function int printSubSets(int num_of_bits, int num)
If (num >= 0)
Print "{ "
Call function subset(num_of_bits - 1, num, num_of_bits)
Print "}"
Call function printSubSets(num_of_bits, num - 1)
Else
Return 0
Return 1
Step 3 → In function int main()
Declare and initialize int n = 4
Call fucntionprintSubSets(n, (int) (pow(2, n)) -1)
Stop उदाहरण
#include <stdio.h>
#include <math.h>
// This function recursively prints the
// subset corresponding to the binary
// representation of num.
int subset(int bitn, int num, int num_of_bits) {
if (bitn >= 0) {
// Print number in given subset only
// if the bit corresponding to it
// is set in num.
if ((num & (1 << bitn)) != 0) {
printf("%d ", num_of_bits - bitn);
}
// Check the next bit
subset(bitn - 1, num, num_of_bits);
}
else
return 0;
return 1;
}
//function to print the subsets
int printSubSets(int num_of_bits, int num) {
if (num >= 0) {
printf("{ ");
// Printint the subsets corresponding to
// the binary representation of num.
subset(num_of_bits - 1, num, num_of_bits);
printf("}");
// recursively calling the function to
// print the next subset.
printSubSets(num_of_bits, num - 1);
}
else
return 0;
return 1;
}
//main program
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 }{ }