Generate power set of a given set

Given a set S, generate all subsets of it i.e., find power set of set S. A power set of any set S is the set of all subsets of S, including the empty set and S itself.

 
For example, if S is the set {x, y, z}, then the subsets of S are:

  • {} (also known as the empty set or the null set)
  • {x}
  • {y}
  • {z}
  • {x, y}
  • {x, z}
  • {y, z}
  • {x, y, z}

and hence the power set of S is {{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}.
 


 

Approach 1: (Using Recursion)

The problem is very similar to 0/1 knapsack problem where for each element in set S, we have two choices –

1. Consider that element
2. Don’t consider that element

In the solution below, we will generate all combinations of subsets by using above logic.

 
C++ implementation –
 

Download   Run Code

Output:

3 2 1
3 2
3 1
3
2 1
2
1

 

Approach 2:

For a given set S, the power set can be found by generating all binary numbers between 0 to 2n-1 where n is the size of the given set.

For example, for set S {x, y, z}, we generate binary numbers from 0 to 23-1 and for each number generated, the corresponding set can be found by considering set bits in the number.

  • 0 = 000 = {}
  • 1 = 001 = {z}
  • 2 = 010 = {y}
  • 3 = 011 = {y, z}
  • 4 = 100 = {x}
  • 5 = 101 = {x, z}
  • 6 = 110 = {x, y}
  • 7 = 111 = {x, y, z}

C++ implementation –
 

Download   Run Code

Output:

1
2
1 2
3
1 3
2 3
1 2 3

Time complexity of both solutions is O(n.2n) where n is the size of the given set.
 
References:
https://en.wikipedia.org/wiki/Power_set

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂