สมมุติว่าเรามีเลข k ค้นหาชุดค่าผสมที่เป็นไปได้ทั้งหมดของตัวเลข k-bit กับ n set-bits โดยที่ 1 <=n <=k ด้วยเหตุนี้ เราจะพิมพ์ตัวเลขทั้งหมดที่มีชุดบิตหนึ่งชุดก่อน ตามด้วยตัวเลขที่มีชุดบิตสองชุด จนถึงจำนวนที่ตั้งค่าบิตทั้งหมดไว้ หากตัวเลขสองตัวมีจำนวนบิตเซ็ตเท่ากัน ตัวเลขที่น้อยกว่าจะมาก่อน ดังนั้นหาก k =3 ตัวเลขจะเป็น [001, 010, 100, 011, 101, 110, 111]
ที่นี่เราจะใช้วิธีการเขียนโปรแกรมแบบไดนามิกเพื่อค้นหาการรวมกันของตัวเลข k-bit กับ n set-bits โดยที่ 1 <=n <=k ปัญหานี้ยังสามารถแบ่งออกเป็นสองส่วน เราจะพบชุดค่าผสมของความยาว k โดยที่ n จำนวน 1s จะเติมนำหน้า 0 ให้กับชุดค่าผสมของความยาว k – 1 ที่มี n ตัว และ 1 ของความยาวรวมกัน 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
