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.

C++

Download   Run Code

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.

C++

Download   Run Code

Output:

1 1 2

1
1 2
1 1
2

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





Leave a Reply

Notify of
avatar
wpDiscuz