# Power gain of a given set

Given a set, I want to display all subsets of it (its cardinality set). I found this code:

```
void printPowerSet(char *set, int set_size)
{
/*set_size of power set of a set with set_size
n is (2**n -1)*/
unsigned int pow_set_size = pow(2, set_size);
int counter, j;
/*Run from counter 000..0 to 111..1*/
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");
}
}
```

I cannot figure out why this part is being used

```
if(counter & (1<<j))
```

what is its meaning?

Time complexity for this algorithm `O(n2^n)`

is there a better method?

source to share

This one `if`

checks if a bit is set `j`

. For example, when `j == 0`

we look (I'm using 8 bits for simplicity):

`XXXXXXX? & 00000001`

where `X`

"doesn't care" `?`

is what we want to test. Then when`j == 1`

`XXXXXX?X & 00000010`

In other words, it is a convenient way to check if a bit is set or not, which determines whether the corresponding set item is included in the current set or not.

In terms of complexity, since there are `2^n`

sets in a cardinality set, it is difficult to imagine a faster algorithm for creating them.

The reason the power set is generated is because the binary counter runs out of all bit value combinations `n`

, see below for an example.

** Example**

set: {1, 2, 3}

```
counter 1<<j intermediate result final
000 001 N/A
000 010 N/A
000 100 N/A
{}
001 001 3
001 010 N/A
001 100 N/A
{3}
< ... skip a few iterations ... >
101 001 3
101 010 N/A
101 100 1
{1,3}
< ... etc ... >
```

source to share

This code below stops faster than the specified algorithm.

Complexity, your estimate is correct since O (N * 2 ^ N) is the size of the output.

```
unsigned c;
for (counter = 0; counter < pow_set_size; counter++) {
for (c = counter; c != 0; ) {
if( c & 1 ) {
printf("%c", set[j]);
}
c = c >> 1; // drop lsb
}
printf("\n");
}
```

source to share