kushal.p1699's blog

By kushal.p1699, history, 5 weeks ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +33
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kushal.p1699 (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please tell us what is the time complexity? O(n^2)?

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

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, # |
  Vote: I like it +13 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Looks like there's a typo in the code: subset.push_back(a[index)]; shouldn't the ) and ] be switched around?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, Genius3435. I've edited the post I hope now it is correct.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it
    for (int i=0; i<(1<<n); i++) {
            vector<int>subset
            for (int j=0; j<n; j++) {
                if (i&(1<<j)) {
                    subset.push_back(j);
                }
            }
        }
    
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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