Hi all, I'm so excited to write my first blog here.

Last week I was helping my friend in tracing the recursion problem called **Generating subset**. He had the code snippet, but he was not able to understand the flow of the program. So, I tried to explain the logic to him. I'm happy that, my explanation made him clear on his doubts. I thought of sharing my explanation on tracing this problem by writing a new blog.

**Problem statement:**

Generate the subsets of given **N** elements using recursion.

**Input:**

1 2 3

**output:**

1 2 3

1 2

1 3

1

2 3

2

3

**Explanation:**

Subsets of [1,2,3] is null, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}.

**code:**

```
#include <bits/stdc++.h>
using namespace std;
vector<int> subset;
void solve(int a[], int n, int index) {
if(index == n){
// print the subset
for(int i=0; i<subset.size(); i++){
cout << subset[i] << " ";
}
cout << "\n";
}else{
subset.push_back(a[index]);
solve(a, n, index+1);
subset.pop_back();
solve(a, n, index+1);
}
}
int main() {
int a[] = {1, 2, 3};
int n = sizeof(a)/sizeof(a[0]);
int startIndex = 0;
solve(a, n, startIndex);
return 0;
}
```

My explanation of this program is given below.

This is my first blog ever in my life. If you find any mistakes or you have any suggestions, please let me know. So that I can improve it form next time.

Thank you.

Auto comment: topic has been updated by kushal.p1699 (previous revision, new revision, compare).Can you please tell us what is the time complexity? O(n^2)?

Should be $$$O(2^n)$$$ as there are $$$2^n$$$ subsets..

Thank you.

I hate to be that guy but shouldn't the complexity be $$$O(n \cdot 2^n)$$$? We have to generate and print each subset.

yes

Yes, It is O(2^n).

Dude you are just a noobie. No one is going to take this blog seriously due to that. This is a very basic concept, everyone on CF already knows this.

You're one to talk, being unrated and all

I appreciate your efforts but this is like Leetcode and GeeksForGeeks article, better be there, don't take it harshly.

Thanks, I will take this as a suggestion.

Looks like there's a typo in the code:

`subset.push_back(a[index)];`

shouldn't the`)`

and`]`

be switched around?Thanks, Genius3435. I've edited the post I hope now it is correct.

Hey, Can anyone tell me which is the efficient way to solve this problem?

That's the most efficient way, $$$O(N \cdot 2^N)$$$ is the theoretical limit, because you have to print out $$$N \cdot 2^{N-1}$$$ numbers total (each number is part of $$$2^{N-1}$$$ subsets).

But the thing about this recursive approach is it's slower to write in a competition. So what many people (including me) do is use binary numbers:

You have an array $$$a$$$ with length $$$n$$$. Generate all binary strings of length $$$n$$$, and call the $$$i$$$'th one $$$b_i$$$. Generate the subset by including the $$$j$$$'th number if the $$$j$$$'th bit of $$$i$$$ (or the $$$j$$$'th character of $$$b_i$$$) is a $$$1$$$. This technique is commonly called a bitmask.

I believe that although this way has the same time complexity, $$$O(N \cdot 2^N)$$$, it has a lower constant factor than the recursive approach.

An example of code for this:PS: Bitmasks are often useful if you're partitioning an array into two disjoint arrays, so a $$$0$$$ at position $$$i$$$ means $$$a_i$$$ goes into the first array, and a $$$1$$$ means $$$a_i$$$ goes into the second array.

Thank you @Genious3435.

When I was beginner, this was nightmare for me to understand