Power Set

Problem Statement:

You are given a set, you need to find all the subsets of that set.

Example

set = {a, b, c}
Power set = {{}, {a}, {b}, {c}, {a, b}, {a,c}, {b, c}, {a, b, c}}

Solution

The solution is very simple.

First we get the size of the power set. We get the powerset size by using pow(2, set_size) formula.

Then we run a loop from 0 to power_set_size, then if the ith bit is set, then we print those elements.

Example:

If we have a set {a, b, c}

The power set size will be 2^3 = 8

Then we run a loop from 0 to 8, and for every set bit, we print the value

   c  b  a    Subset
0  0  0  0    {}
1  0  0  1    {a}
2  0  1  0    {b}
3  0  1  1    {ab}
4  1  0  0    {c}
5  1  0  1    {ac}
6  1  1  0    {bc}
7  1  1  1    {abc}

Here the time complexity will be O(n2^n)

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;

void print_power_set(char *set, int set_size) 
{ 

   int pow_set_size = pow(2, set_size); 
    int counter;
    int j; 
  
    for(counter = 0; counter < pow_set_size; counter++) 
    { 
       for(j = 0; j < set_size; j++) 
       { 
           if(counter & (1 << j)) 
               cout << set[j]; 
       } 
     cout << endl; 
    } 
} 

int main() 
{ 
    char set[] = {'a','b','c'}; 
    print_power_set(set, 3); 
    return 0; 
} 

Output:

a
b
ab
c
ac
bc
abc