Perhaps today and/or tomorrow due to a power outage there may be disruptions in the work of Codeforces and Polygon. Please do not plan any important events during this time. If there are details or the exact time, we will definitely publish them. Estimated time of maintenance: from 2 Aug, 16:00 (UTC) to 2 Aug, 20:00 (UTC). ×

Generating Subsets (Recursion)

Revision en1, by kushal.p1699, 2021-05-09 16:16:33

# Generating Subsets (Recursion)

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 subset;
void search(int a[], int n, int index) {
if(index == n){
// print the subset
for(int i=0; i<< subset[i] << " ";
}
cout << "\n";
}else{
subset.push_back(a[index)];
search(a, n, index+1);
subset.pop_back();
search(a, n, index+1);
}
}

int main() {
int a[] = {1, 2, 3};
int n = sizeof(a)/sizeof(a[0]);
int startIndex = 0;
search(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.

#### History

Revisions

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