### kushal.p1699's blog

By kushal.p1699, history, 5 weeks ago,

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.

• +33

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by kushal.p1699 (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 Can you please tell us what is the time complexity? O(n^2)?
•  » » 5 weeks ago, # ^ |   +2 Should be $O(2^n)$ as there are $2^n$ subsets..
•  » » » 5 weeks ago, # ^ |   0 Thank you.
•  » » » 5 weeks ago, # ^ |   +15 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.
•  » » » » 5 weeks ago, # ^ |   0 yes
•  » » 5 weeks ago, # ^ |   0 Yes, It is O(2^n).
 » 5 weeks ago, # |   -13 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.
•  » » 5 weeks ago, # ^ |   +12 You're one to talk, being unrated and all
 » 5 weeks ago, # |   +13 I appreciate your efforts but this is like Leetcode and GeeksForGeeks article, better be there, don't take it harshly.
•  » » 5 weeks ago, # ^ |   0 Thanks, I will take this as a suggestion.
 » 5 weeks ago, # |   +4 Looks like there's a typo in the code: subset.push_back(a[index)]; shouldn't the ) and ] be switched around?
•  » » 5 weeks ago, # ^ |   0 Thanks, Genius3435. I've edited the post I hope now it is correct.
 » 5 weeks ago, # |   0 Hey, Can anyone tell me which is the efficient way to solve this problem?
•  » » 5 weeks ago, # ^ |   +14 for (int i=0; i<(1<subset for (int j=0; j
•  » » 5 weeks ago, # ^ |   0 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:// !(mask >> N) checks that the N'th bit isn't set // Because if it is, that means we have already // checked all possible subsets and can stop now. for (int mask = 0; !(mask >> N); mask++) { for (int j = 0; j < N; j++) if ((mask >> j) & 1) cout << a[j] << ' '; cout << '\n'; } 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.
•  » » » 5 weeks ago, # ^ |   0 Thank you @Genious3435.
 » 5 weeks ago, # |   +4 When I was beginner, this was nightmare for me to understand