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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of