## DEV Community is a community of 618,434 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Nlogn

# Find all possible subset of a given set

mayank joshi Originally published at nlogn.in γ»Updated on γ»2 min read

Given a set (of n elements), Print all possible subset (2^n) of this set.
Example: Set = {a,b,c}, Power set of S, P(S) = {Ξ¦, {a}, {b}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c}}

Note: A set of n elements will have 2^n elements in its power set.

We will use the concept of binary number here. Given n bits, 2^n binary numbers are possible.
An element will be chosen for the power set if itβs corresponding bit will be one.
Each element of a given set will be by one bit. Each element of a given set will be by one bit. An element will be chosen for the power-set only if its corresponding bit is one.

``````Example: S={a,b,c}; n = 3; 2^n = 2^3 = 8
a is represented by 0th bit (Least significant Bit)
b is represented by 1st bit
c is represented by 2nd bit (Most Significant Bit)

0 ->  000 -  empty set
1 ->  001 -  {a}
2 ->  010 -  {b}
3 ->  011 -  {a,b}
4 ->  100 -  {c}
5 ->  101 -  {c,a}
6 ->  110 -  {b,c}
7 ->  111 -  {a,b,c}
``````

### ALGORITHM

``````find_subset(set, set_size){
n = power(2,set_size);
for(i=0; i<n; i++){
//j will run set_size times to check each bit
for(j=0; j<set_size; j++}
if(current bit is 1(set))
print(corresponding set element)
}
}
``````

### Output

``````{  }
{ a }
{ b }
{ ab }
{ c }
{ ac }
{ bc }
{ abc }
{ d }
{ bd }
{ abd }
{ cd }
{ acd }
{ bcd }
{ abcd }
``````

### Time Complexity

The time complexity of the above program is O(n*2^n), where n is the number of elements in the set.
The first loop that runs through powerset( 2^set_size) has complexity 2^n and the nested loop, which runs n(set size) times to check if each of n elements is one has complexity n.

This post was originally published at nlogn.inπ