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].
