DEV Community

loading...
Nlogn

Find all possible subset of a given set

mayankjoshi profile image mayank joshi Originally published at nlogn.in ・Updated on ・2 min read

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)

pic
Editor guide