Bit- Manipulation : finding subset

What is the logic behind finding subset using bit manipulation?

Here’s the code:-

for(counter = 0; counter < pow_set_size; counter++)
{
for(j = 0; j < set_size; j++)
{

      if(counter & (1<<j))      
        printf("%c", set[j]);
   }
   printf("\n");
} 

source :- Power Set - GeeksforGeeks

Assume your set has 3 elements - A, B, C
It can form 2^3 subsets.

The subsets are - {}, {A}, {B}, {C}, {A,B}, {B,C}, {A,C}, {A,B,C}

But why 2^3 ?

Notice, that each time I create a subset, for every element in the set I can choose to include or exclude that particular element. These are the choices I have for each element.
For 1, its 2 choices.
For 2, its 2x2 choices.
And, for 3, its 2x2x2 (2^3) choices.

So, we represent this binary choice (as there are only 2: include and exclude) with 1s and 0s.
We write 1 to indicate we are choosing the element, and we write 0 to indicate we are excluding the element.

Example - {A,C} can be written as 101.
I.e. - from A,B,C we have taken A, not taken B, and taken C.

Using this we can represent every subset, and we can access them by reading the binary values from 0-(2^N-1) where N is the number of elements in the set. (Also notice, 0 refers to the NULL set)

So we run a loop from 0 to (2^N-1) and for each of those we decipher what is the subset by looking at the binary value at that index.

Example - 000 = {}; 001={C}; 010 = {B}; 011= {B,C}; 100={A}; 101={A,C}; 110={A,B}; 111={A,B,C};

Hope I could clear your doubts. :slight_smile:

2 Likes