How to print all unique subsets of a set, using recursion and bit-manipulation.

flashy thumbnail, xd

Here’s my quick two cents on how to solve this problem:

RECURSIVE APPROACH

Let’s consider an example, suppose we’re given with a set [1,2,3] and we’ve to get all of it’s unique subsets, let’s take a very intuitive approach to it:

[1,2,3], for every element that appears in this set, I have two choices, either I can choose it or not choose it. Let’s build subsets of the set [1,2,3] using this principle.

1. [], I chose nothing, so an empty string.
2. [1], I chose ‘1’ and rejected both ‘2’ and ‘3’.
3. [1,2], I chose ‘1’, ‘2’ and rejected ‘3’.
4. [1,2,3], I chose ‘1’, ‘2’, and ‘3’, all three of them.
5. [2], I chose only ‘2’.
6. [2,3], I chose ‘2’ and ‘3’.
7. [3], I chose only ‘3’ and rejected ‘1’ and ‘2’.

as you can see there are a total of 8 unique subsets that can be built by a set of size 3. Does this ring some bells? Well, for every element we have 2 choices, either to take it or not take it, so for n elements we’ll have 2^n choices. yes? great!!

By now you must be wondering how can we approach this problem in a recursive manner, and first of all how to even know that this is a recursion problem, right?

Alright, Alright, Alright, hold my beer.

Have a clear look at the crux of this problem, starting from the first element to the last, we have to make a choice, either to take it or not. And with every choice our original set is decreasing in size. Bang!! that’s very very recurring…that’s how we spot recursion.

Base Case : How to decide on the base case of this problem? what actually is the base case, the case for which we want the recursion tree to stop? yes, but let’s boil it down further: Base Case is the smallest valid input, umm then what could be the smallest valid input in this set [1,2,3]? Okay, suppose we made choices for 1, 2, and 3, what is left now? empty set? yes, so that will be our smallest valid input, but when the set will be empty we want our recursion to stop, and hence when our set will be empty we’ll stop our recursion.

let me draw a recursion tree for this particular set[1,2,3].

recursive tree for set[1,2,3]

what can we observe here? We can see that for every choice, whether to choose an element or to reject it we’re calling our recursive function. And what do the leaf nodes depict? end of our recursion and we’re stopping our recursion when the set[1,2,3] becomes empty.

By making choices in recursion we’re also making our input smaller, initially we had the set[1,2,3] and after we decided for 1, it got smaller to [2,3].

Here’s the recursive code:

recursive solution

Here at any instance we're creating two separate subsets one that contains our choice element another that doesn't. Then using both of those two sets we're making two recursive calls.

Accepted on LeetCode

BIT-MANIPULATION APPROACH

For this we require a prerequisite information, in a binary number to check if it’s ‘i’ bit is set(1) or not(0) we use a special technique.

Suppose we have a binary number: 10101101 for this number the 4th bit is set(1), but how to check whether it’s set or not, programmatically? We can simply do a logical & of this number with 1<<(4-1) = 00001000 if the 4th digit will be set then the output will be non-zero otherwise it’ll be zero.

if(n&(1<<(i-1)) != 0) then 'i' bit is set(1)

great now, let’s see how we use Bit-manipulation technique to solve this problem, for a set of size 3 we’ll have 2^n subsets? Let’s also represent number from 0 to 2^n-1 in binary.

0 : 000
1 : 001
2 : 010
3 : 011
4 : 100
5 : 101
6 : 110
7 : 111

Here every set bit(1) represents that we’re taking that element in our set, let’s take an example of 0 : 000 we’re taking none of the elements hence subset: [] , for 1 : 001 we’re taking last elements and hence subset: [3] , for 2 : 010 we’re taking the middle element hence subset: [2] for 6 : 110 we’re taking first and second element, hence subset: [1,2] for 7 : 111 we’re taking all three elements, and hence the subset: [1,2,3]

Here’s the code that does the same:

bit-manipulation solution

both the approaches are equally interesting, but I’ve always had a strong yearning for Recursion(lol, most nerdy thing to say), umm, it’s more intuitive after all.

Both the solutions have a time complexity of O(n*2^n). Space complexity will also be O(n*2^n) because we’re storing, n sized 2^n sets.

Accepted on LeetCode

Bye Bye!!