मान लीजिए कि हमारे पास एक संख्या k है। n सेट-बिट्स के साथ k-बिट संख्याओं के सभी संभावित संयोजन खोजें जहां 1 <=n <=k. परिणामस्वरूप हम सभी नंबरों को पहले एक सेट बिट के साथ प्रिंट करेंगे, उसके बाद दो बिट्स सेट वाली संख्याएं, उस संख्या तक जहां सभी बिट्स सेट हैं। यदि दो संख्याओं में सेट बिट्स की संख्या समान है, तो छोटी संख्या पहले आती है। तो यदि k =3 है, तो संख्याएँ [001, 010, 100, 011, 101, 110, 111]
होंगी।यहां हम n सेट-बिट्स के साथ k-बिट संख्याओं के सभी संभावित संयोजनों को खोजने के लिए गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे जहां 1 <=n <=k। इस समस्या को भी दो भागों में बांटा जा सकता है। हम लंबाई k के सभी संयोजन पाएंगे जहां n संख्या 1s, n वाले के साथ k – 1 के सभी संयोजनों के लिए 0 और लंबाई k – 1 के सभी संयोजनों को n – 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