查找设置了n位的k位数字的所有组合，其中1-yiteyi-C++库

给定一个数字k，找出k位数字与n位集合的所有可能组合，其中1<=n<=k。解决方案应首先打印一个集合位的所有数字，然后打印两个集合位的数字，。。最多可设置所有k位的数字。如果两个数字的设置位数相同，则应先使用较小的数字。

null

例如：

Input: K = 3
Output:  
001 010 100 
011 101 110 
111 

Input: K = 4
Output:  
0001 0010 0100 1000 
0011 0101 0110 1001 1010 1100 
0111 1011 1101 1110 
1111 

Input: K = 5
Output:  
00001 00010 00100 01000 10000 
00011 00101 00110 01001 01010 01100 10001 10010 10100 11000 
00111 01011 01101 01110 10011 10101 10110 11001 11010 11100 
01111 10111 11011 11101 11110 
11111

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

我们需要找到k位数字与n个集合位的所有可能组合，其中1<=n<=k。如果我们仔细分析，我们会发现这个问题可以进一步划分为子问题。我们可以通过在长度为k-1和n-1的所有组合前加0，在长度为k-1和n-1的所有组合前加1，来找到长度为k和n-1的所有组合。我们可以使用动态规划来保存子问题的解决方案。

以下是C++实现上述思想的方法——

                     // C++ program find all the possible combinations of                   
                     // k-bit numbers with n-bits set where 1 <= n <= k                   
                     #include <iostream>                   
                     #include <vector>                   
                     using                               namespace                               std;                   
                     // maximum allowed value of K                   
                     #define K 16                   
                             
                     // DP lookup table                   
                     vector<string> DP[K][K];                   
                             
                     // Function to find all combinations k-bit numbers with                   
                     // n-bits set where 1 <= n <= k                   
                     void                               findBitCombinations(                               int                               k)                   
                     {                   
                                         string str =                               ""                               ;                   
                             
                                         // DP[k][0] will store all k-bit numbers                   
                                         // with 0 bits set (All bits are 0's)                   
                                         for                               (                               int                               len = 0; len <= k; len++)                   
                                         {                   
                                         DP[len][0].push_back(str);                   
                                         str = str +                               "0"                               ;                   
                                         }                   
                             
                                         // fill DP lookup table in bottom-up manner                   
                                         // DP[k][n] will store all k-bit numbers                   
                                         // with n-bits set                   
                                         for                               (                               int                               len = 1; len <= k; len++)                   
                                         {                   
                                         for                               (                               int                               n = 1; n <= len; n++)                   
                                         {                   
                                         // prefix 0 to all combinations of length len-1                   
                                         // with n ones                   
                                         for                               (string str : DP[len - 1][n])                   
                                         DP[len][n].push_back(                               "0"                               + str);                   
                             
                                         // prefix 1 to all combinations of length len-1                   
                                         // with n-1 ones                   
                                         for                               (string str : DP[len - 1][n - 1])                   
                                         DP[len][n].push_back(                               "1"                               + str);                   
                                         }                   
                                         }                   
                             
                                         // print all k-bit binary strings with                   
                                         // n-bit set                   
                                         for                               (                               int                               n = 1; n <= k; n++)                   
                                         {                   
                                         for                               (string str : DP[k][n])                   
                                         cout << str <<                               " "                               ;                   
                             
                                         cout << endl;                   
                                         }                   
                     }                   
                             
                     // Driver code                   
                     int                               main()                   
                     {                   
                                         int                               k = 5;                   
                                         findBitCombinations(k);                   
                             
                                         return                               0;                   
                     }                   

输出：

00000 
00001 00010 00100 01000 10000 
00011 00101 00110 01001 01010 01100 10001 10010 10100 11000 
00111 01011 01101 01110 10011 10101 10110 11001 11010 11100 
01111 10111 11011 11101 11110 
11111

本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章

查找设置了n位的k位数字的所有组合，其中1<=n<=k按排序顺序排列

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。