Power set i.e all subset of a set can be found by

- Using Tree representation approach
- Using Bit manipulation approach

**Tree Representation Approach**

There are 2 possibilities for each item of a set, It will be either included in a subset or not included.

Based on this fact, Lets draw a Tree for given Set [a, b, c].

There are 2 possibilities of “a”. It will be either included in a subset or not included. Similarly, for each possibilities of “a”, again there are 2 possibilities for “b”. “b” will be included for each possibilities of “a” or not included.

**Bit Manipulation Approach**

In this approach we will use Bits Manipulation for printing Subset of a set. Before going ahead, first lets understand how to check any bit is set in a byte. Binary representation of a number 1 = 0001, 2 = 0010, …., 5 = 0101, ….

If we want to check nth bit is set in a number,

- We will first take binary representation of 1 (0001),
- Move the LSB in binary representation of 1 to nth position.

Eg: If we want to check whether bit at position 2 is set, then move 1 two times on right side,

= 1 << 2

= 0001 << 2

= 0100 (Let this is**B**) - Once the LSB of binary 1 is moved to nth position, do logical AND of number and
**B.**If the result is greater than 0, then the bit is set, not otherwise.

**If we want to find subset of 3 characters [a, b, c], then how many total subset can be made out of it? **

The number of subsets equals to 2 to the power of the number of elements in the set. Number of subsets that can be made from set of 3 characters [a, b, c] is 2^3 = 8 subsets. So, If there are n characters [a, b, c…. n] in a set, then there will be 2^n total subsets.

**How to find total number of subsets possible using bit manipulation?**

By shifting the bit representation of the number 1 by n, we will get 2^n. Thus, if we shift the bit string of 1 by the number of elements in the given set, we’ll get the number of subsets for that set.

For example, if we have S = [a, b, c], length of set here is 3. So for finding total subsets, we have to shift binary 1 by 3 times. If we compare subset of [a, b, c] to binaries representation of numbers from 0 to 7, we can find a relation with the bit sets in each number to subsets of [a, b, c].