Print all distinct Subsets of a given Set

Given a set S, generate all distinct subsets of it i.e., find distinct 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, x}, then the subsets of S are:

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

Therefore, distinct subsets in the power set of S are:

{ {}, {x}, {y}, {x, y}, {x, x}, {x, y, x} }.

Approach 1: (Using Recursion)

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

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

In the solution below, we generate all combinations of subsets by using above logic. To print only distinct subsets, we initially sort the subset and exclude all adjacent duplicate elements from the subset along with the current element in case 2.

Output:

3 1 1
3 1
3
1 1
1

Java

Output:

[3, 1, 1]
[3, 1]
[3]
[1, 1]
[1]
[]

The time complexity of above solution is O(n.2n) where n is the size of the given set.

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}

To avoid printing duplicates subsets, we initially sort the set. Also, we insert each subset into the set. As set maintains all distinct combinations, we will have only distinct subsets into the set.

Output:

1 1 2

1
1 2
1 1
2

Java

Output:

1 1
1 2
1 1 2
2
1

The time complexity of above solution is O(n.2n) where n is the size of the given 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 🙂