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. Each element of a given set will be represented by a single 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

#include <bits/stdc++.h> using namespace std; int find_subsets(string str, int size){ int n = pow(2,size); //binary counter running from 0 to 2^n -1 for(int i=0; i<n; i++){ cout<<"{ "; //this loop will run n time to check each of the n bits for(int j=0; j<size; j++){ //check if the jth bit is one and if it is set(one), print corresponding element if(i&(1<<j)) cout<<str[j]<<""; } cout<<" }"<<endl; } return 0; } int main() { string str = "abcd"; find_subsets(str, str.size()); return 0; }

#### 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.