在Java中查找给定集合的所有子集-yiteyi-C++库

问题： 找到给定集合的所有子集。

null

Input: S = {a, b, c, d}Output:{}, {a} , {b}, {c}, {d}, {a,b}, {a,c},{a,d}, {b,c}, {b,d}, {c,d}, {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d}, {a,b,c,d}

任何给定集合的子集总数等于2^（集合中的元素数）。如果我们仔细注意到它只是0到15之间的二进制数，可以如下所示：

0000	{}
0001	{a}
0010	{b}
0011	{a，b}
0100	{c}
0101	{a，c}
0110	{b，c}
0111	{a，b，c}
1000	{d}
1001	{a，d}
1010	{b，d}
1011	{a，b，d}
1100	{c，d}
1101	{a，c，d}
1110	{b，c，d}
1111	{a，b，c，d}

从右边开始，第i个位置的1表示集合的第i个元素存在，0表示该元素不存在。因此，我们要做的就是生成从0到2^n–1的二进制数，其中n是集合的长度或集合中元素的数量。

JAVA

                         // A Java program to print all subsets of a set                       
                         import                                     java.io.IOException;                       
           
                         class                                     Main                       
                         {                       
                                                 // Print all subsets of given set[]                       
                                                 static                                     void                                     printSubsets(                                     char                                     set[])                       
                                                 {                       
                                                 int                                     n = set.length;                       
           
                                                 // Run a loop for printing all 2^n                       
                                                 // subsets one by one                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < (                                     1                                     <<n); i++)                       
                                                 {                       
                                                 System.out.print(                                     "{ "                                     );                       
           
                                                 // Print current subset                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j < n; j++)                       
           
                                                 // (1<<j) is a number with jth bit 1                       
                                                 // so when we 'and' them with the                       
                                                 // subset number we get which numbers                       
                                                 // are present in the subset and which                       
                                                 // are not                       
                                                 if                                     ((i & (                                     1                                     << j)) >                                     0                                     )                       
                                                 System.out.print(set[j] +                                     " "                                     );                       
           
                                                 System.out.println(                                     "}"                                     );                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 char                                     set[] = {                                     'a'                                     ,                                     'b'                                     ,                                     'c'                                     };                       
                                                 printSubsets(set);                       
                                                 }                       
                         }                       

输出：

{ }{ a }{ b }{ a b }{ c }{ a c }{ b c }{ a b c }

时间复杂度：O（n*（2^n）），因为外循环运行O（2^n），内循环运行O（n）。 相关帖子： 在C/C中求集合的所有子集++ 本文由 尼希尔·特克瓦尼。 如果你喜欢Geeksforgek，并想贡献自己的力量，你也可以写一篇文章，然后把你的文章发到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

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

THE END

技术文章