Generating Subsets (Recursion)

Revision en4, by kushal.p1699, 2021-05-09 17:50:30

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.

Tags #c++, #recursion, #subset, #tracing, #cp, #codefoces, #firstblog

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English kushal.p1699 2021-05-10 07:25:18 2 Tiny change: 'ck(a[index)];\n ' -> 'ck(a[index]);\n '
en4 English kushal.p1699 2021-05-09 17:50:30 49 Tiny change: ' subset[i] << " ";\n ' -> ' subset[i];\n '
en3 English kushal.p1699 2021-05-09 16:19:59 34
en2 English kushal.p1699 2021-05-09 16:17:02 50 Tiny change: 'Generating Subsets (Recursion)\n==================\nHi all, ' -> '\nHi all, '
en1 English kushal.p1699 2021-05-09 16:16:33 1720 Initial revision (published)