Algorithms‎ > ‎Misc‎ > ‎

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
011                    -> ab
100                     -> c
101                     -> ac
110                     -> bc
111                     -> abc
```

Program:

 `#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 pront jth element from set */``          ``if``(counter & (1<

Time Complexity: O(n2^n)