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

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promsie, we won't spam
Even we hate spam as much as you hate them

Books recommendation for interview preparation