मान लीजिए हमारे पास एक संख्या k है। k-बिट संख्याओं के सभी संभावित संयोजन खोजें जिनमें n सेट-बिट हों जहां 1 <= n <= k। परिणाम के रूप में हम पहले एक सेट बिट वाली सभी संख्याएं प्रिंट करेंगे, उसके बाद दो बिट सेट वाली संख्याएं, उस संख्या तक जहां सभी बिट सेट हों। यदि दो संख्याओं में समान संख्या में सेट बिट हैं, तो छोटी संख्या पहले आएगी। तो यदि k = 3, तो संख्याएं [001, 010, 100, 011, 101, 110, 111] होंगी।
यहां हम डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे ताकि 1 <= n <= k के साथ n सेट-बिट वाली k-बिट संख्याओं के सभी संभावित संयोजन खोज सकें। इस समस्या को दो भागों में भी विभाजित किया जा सकता है। हम लंबाई k के सभी संयोजन खोजेंगे जहां n संख्या में 1s होंगे, लंबाई k-1 के n ones वाले सभी संयोजनों को 0 से प्रीफिक्स करके और लंबाई k-1 के n-1 ones वाले सभी संयोजनों को 1 से प्रीफिक्स करके।
उदाहरण
#include <iostream>
#include <vector>
#define K 16
using namespace std;
vector<string> table[K][K];
void getCombinations(int k) {
string str = "";
for (int bit = 0; bit <= k; bit++) {
table[bit][0].push_back(str);
str = str + "0";
}
for (int bit = 1; bit <= k; bit++) {
for (int n = 1; n <= bit; n++) {
for (string str : table[bit - 1][n])
table[bit][n].push_back("0" + str);
for (string str : table[bit - 1][n - 1])
table[bit][n].push_back("1" + str);
}
}
for (int n = 1; n <= k; n++) {
for (string str : table[k][n])
cout << str << " ";
cout << endl;
}
}
int main() {
int k = 4;
getCombinations(k);
}
आउटपुट
0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111
