查找具有n位设置的k位数字的所有组合，其中1 <= n <= k按C ++排序

假设我们有一个数字k。查找具有n个置位的k位数字的所有可能组合，其中1 <= n <= k。结果，我们将首先打印一个设置位的所有数字，然后再打印设置两个位的数字，直到所有位被设置的数字。如果两个数字的置位位数相同，则较小的数字优先。因此，如果k = 3，则数字将为[001，010，100，011，101，110，111]

在这里，我们将使用动态编程方法找到具有n个置位的k位数字的所有可能组合，其中1 <= n <= k。这个问题也可以分为两个部分。我们将找到长度为k的所有组合，其中n等于1时，将长度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