숫자 k가 있다고 가정합니다. 1 <=n <=k인 n 세트 비트가 있는 k 비트 수의 가능한 모든 조합을 찾습니다. 결과적으로 우리는 모든 비트가 설정된 숫자까지 1비트가 먼저 설정된 모든 숫자를 인쇄한 다음 2비트가 설정된 숫자를 인쇄합니다. 두 숫자의 설정 비트 수가 같으면 작은 숫자가 먼저 옵니다. 따라서 k =3이면 숫자는 [001, 010, 100, 011, 101, 110, 111]
이 됩니다.여기에서 1 <=n <=k인 n 세트 비트가 있는 k 비트 숫자의 가능한 모든 조합을 찾기 위해 동적 프로그래밍 접근 방식을 사용할 것입니다. 이 문제는 또한 두 부분으로 나눌 수 있습니다. 길이 k의 모든 조합을 찾을 수 있습니다. 여기서 n개의 1은 길이 k – 1의 모든 조합에 0을 접두사로 붙이고 길이 k – 1의 모든 조합에 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