Cho k, tìm tất cả chuỗi k-bit có n bit 1 (1≤n≤k). In theo thứ tự: trước các chuỗi có 1 bit 1, sau 2 bit 1,... Cùng số bit 1 thì số nhỏ hơn trước. Ví dụ k=3 → 001 010 100 011 101 110 111.
Quy hoạch động: table[bit][n] lưu các chuỗi độ dài bit có n bit 1. table[bit][n] = '0'+table[bit-1][n] ∪ '1'+table[bit-1][n-1].
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); }
Kết quả
0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111