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)
}
}
```

### Implementation of the above algorithm in CPP

### Output

`{ }`

{ a }

{ b }

{ ab }

{ c }

{ ac }

{ bc }

{ abc }

{ d }

{ ad }

{ 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*π

## Discussion (0)