# 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

(1 votes, average: 5.00 out of 5)

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 🙂