Giả sử chúng ta có một số k. Tìm tất cả các kết hợp có thể có của số k bit với n bit tập hợp trong đó 1 <=n <=k. Do đó, chúng tôi sẽ in tất cả các số với một bit được thiết lập trước, tiếp theo là các số có hai bit được thiết lập, cho đến số mà tất cả các bit được đặt. Nếu hai số có cùng số bit đặt thì số nhỏ hơn đứng trước. Vì vậy, nếu k =3, thì các số sẽ là [001, 010, 100, 011, 101, 110, 111]
Ở đây chúng ta sẽ sử dụng phương pháp lập trình động để tìm tất cả các kết hợp có thể có của số k-bit với n bit tập hợp trong đó 1 <=n <=k. Vấn đề này cũng có thể được chia thành hai phần. Chúng tôi sẽ tìm tất cả các kết hợp độ dài k trong đó n số 1 sẽ bằng cách thêm tiền tố 0 vào tất cả các kết hợp độ dài k - 1 với n đơn vị và 1 cho tất cả các kết hợp độ dài k - 1 với n - 1 đơn vị.
Ví dụ
#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);
} Đầu ra
0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111