# 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 –

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 –

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

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 🙂

Get great deals at Amazon