# Power Set

Power Set Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.

If S has n elements in it then P(s) will have 2^n elements

Algorithm:

```Input: Set[], set_size
1. Get the size of power set
powet_set_size = pow(2, set_size)
2  Loop for counter from 0 to pow_set_size
(a) Loop for i = 0 to set_size
(i) If ith bit in counter is set
Print ith element from set for this subset
(b) Print seperator for subsets i.e., newline
```

Example:

```Set  = [a,b,c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111

Value of Counter            Subset
000                    -> Empty set
001                    -> a
010                    -> b
011                    -> ab
100                    -> c
101                    -> ac
110                    -> bc
111                    -> abc
```

Program:

## C++

 `// C++ Program of above approach ` `#include ` `#include ` `using` `namespace` `std; ` ` `  `class` `gfg ` `{ ` `     `  `public``: ` `void` `printPowerSet(``char` `*set, ``int` `set_size) ` `{ ` `    ``/*set_size of power set of a set with set_size ` `    ``n is (2**n -1)*/` `    ``unsigned ``int` `pow_set_size = ``pow``(2, set_size); ` `    ``int` `counter, j; ` ` `  `    ``/*Run from counter 000..0 to 111..1*/` `    ``for``(counter = 0; counter < pow_set_size; counter++) ` `    ``{ ` `    ``for``(j = 0; j < set_size; j++) ` `    ``{ ` `        ``/* Check if jth bit in the counter is set ` `            ``If set then print jth element from set */` `        ``if``(counter & (1 << j)) ` `            ``cout << set[j]; ` `    ``} ` `    ``cout << endl; ` `    ``} ` `} ` `}; ` ` `  `/*Driver code*/` `int` `main() ` `{ ` `    ``gfg g; ` `    ``char` `set[] = {``'a'``,``'b'``,``'c'``}; ` `    ``g.printPowerSet(set, 3); ` `    ``return` `0; ` `} ` ` `  `// This code is contributed by SoM15242 `

/div>

## C

 `#include ` `#include ` ` `  `void` `printPowerSet(``char` `*set, ``int` `set_size) ` `{ ` `    ``/*set_size of power set of a set with set_size ` `      ``n is (2**n -1)*/` `    ``unsigned ``int` `pow_set_size = ``pow``(2, set_size); ` `    ``int` `counter, j; ` ` `  `    ``/*Run from counter 000..0 to 111..1*/` `    ``for``(counter = 0; counter < pow_set_size; counter++) ` `    ``{ ` `      ``for``(j = 0; j < set_size; j++) ` `       ``{ ` `          ``/* Check if jth bit in the counter is set ` `             ``If set then print jth element from set */` `          ``if``(counter & (1<

## Java

 `// Java program for power set ` `import` `java .io.*; ` ` `  `public` `class` `GFG { ` `     `  `    ``static` `void` `printPowerSet(``char` `[]set, ` `                            ``int` `set_size) ` `    ``{ ` `         `  `        ``/*set_size of power set of a set ` `        ``with set_size n is (2**n -1)*/` `        ``long` `pow_set_size =  ` `            ``(``long``)Math.pow(``2``, set_size); ` `        ``int` `counter, j; ` `     `  `        ``/*Run from counter 000..0 to ` `        ``111..1*/` `        ``for``(counter = ``0``; counter <  ` `                ``pow_set_size; counter++) ` `        ``{ ` `            ``for``(j = ``0``; j < set_size; j++) ` `            ``{ ` `                ``/* Check if jth bit in the  ` `                ``counter is set If set then  ` `                ``print jth element from set */` `                ``if``((counter & (``1` `<< j)) > ``0``) ` `                    ``System.out.print(set[j]); ` `            ``} ` `             `  `            ``System.out.println(); ` `        ``} ` `    ``} ` `     `  `    ``// Driver program to test printPowerSet ` `    ``public` `static` `void` `main (String[] args) ` `    ``{ ` `        ``char` `[]set = {``'a'``, ``'b'``, ``'c'``}; ` `        ``printPowerSet(set, ``3``); ` `    ``} ` `} ` ` `  `// This code is contributed by anuj_67. `

## Python3

 `# python3 program for power set ` ` `  `import` `math; ` ` `  `def` `printPowerSet(``set``,set_size): ` `     `  `    ``# set_size of power set of a set ` `    ``# with set_size n is (2**n -1) ` `    ``pow_set_size ``=` `(``int``) (math.``pow``(``2``, set_size)); ` `    ``counter ``=` `0``; ` `    ``j ``=` `0``; ` `     `  `    ``# Run from counter 000..0 to 111..1 ` `    ``for` `counter ``in` `range``(``0``, pow_set_size): ` `        ``for` `j ``in` `range``(``0``, set_size): ` `             `  `            ``# Check if jth bit in the  ` `            ``# counter is set If set then  ` `            ``# print jth element from set  ` `            ``if``((counter & (``1` `<< j)) > ``0``): ` `                ``print``(``set``[j], end ``=` `""); ` `        ``print``(""); ` ` `  `# Driver program to test printPowerSet ` `set` `=` `[``'a'``, ``'b'``, ``'c'``]; ` `printPowerSet(``set``, ``3``); ` ` `  `# This code is contributed by mits. `

## C#

 `// C# program for power set ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``static` `void` `printPowerSet(``char` `[]``set``, ` `                            ``int` `set_size) ` `    ``{ ` `        ``/*set_size of power set of a set ` `        ``with set_size n is (2**n -1)*/` `        ``uint` `pow_set_size =  ` `              ``(``uint``)Math.Pow(2, set_size); ` `        ``int` `counter, j; ` `     `  `        ``/*Run from counter 000..0 to ` `        ``111..1*/` `        ``for``(counter = 0; counter <  ` `                   ``pow_set_size; counter++) ` `        ``{ ` `            ``for``(j = 0; j < set_size; j++) ` `            ``{ ` `                ``/* Check if jth bit in the  ` `                ``counter is set If set then  ` `                ``print jth element from set */` `                ``if``((counter & (1 << j)) > 0) ` `                    ``Console.Write(``set``[j]); ` `            ``} ` `             `  `            ``Console.WriteLine(); ` `        ``} ` `    ``} ` `     `  `    ``// Driver program to test printPowerSet ` `    ``public` `static` `void` `Main () ` `    ``{ ` `        ``char` `[]``set` `= {``'a'``, ``'b'``, ``'c'``}; ` `        ``printPowerSet(``set``, 3); ` `    ``} ` `} ` ` `  `// This code is contributed by anuj_67. `

## PHP

 ` `

Output :

```a
b
ab
c
ac
bc
abc```

Time Complexity: O(n2^n)

Recursive program to generate power set

Refer Power Set in Java for implementation in Java and more methods to print power set.

References:
http://en.wikipedia.org/wiki/Power_set

If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to [email protected] See your article appearing on the GeeksforGeeks main page and help other Geeks.

## tags:

Mathematical Mathematical