There are many variations of this problem, I will stay on the general problem of finding all subsets of a set. For example if our set is

*[1, 2, 3]*- we would have*8*(2 to the power of 3) subsets:*{[], [1], [2], [3], [1, 2], [1, 3], [1, 2, 3], [2, 3]}*. So basically our algorithm can't be faster than O(*2^n*) since we need to go through all possible combinations.
There's a few ways of doing this. I'll mention two ways here - the recursive way, that we've been taught in high schools; and using a bit string.

Using a bit string involves some bit manipulation but the final code can be found easy to understand. The idea is that all the numbers from

*0*to*2^n*are represented by unique bit strings of*n*bit width that can be translated into a subset. So for example in the above mentioned array we would have*8*numbers from*0*to*7*inclusive that would have a bit representation that is translated using the bit index as the index of the array.Nr | Bits | Combination |
---|---|---|

0 | 000 | {} |

1 | 001 | {1} |

2 | 010 | {2} |

3 | 011 | {1, 2} |

4 | 100 | {3} |

5 | 101 | {1, 3} |

6 | 110 | {2, 3} |

7 | 111 | {1, 2, 3} |

It may look easier in the code:

Note:

- The

*Math.pow*call computes 2 to the power of n

- The

*findLowestBitSet*is a method I mentioned earlier. In Java it could look like this:

Or it could be optimized to look like this:

For comparison find below the code for the recursive algorithm:

## No comments:

## Post a Comment