Home Practice Programming Find all possible subset of a given set

# Find all possible subset of a given set

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 }
{ 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.