Generating Subsets (Recursion)

Правка en5, от kushal.p1699, 2021-05-10 07:25:18

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.

Теги #c++, #recursion, #subset, #tracing, #cp, #codefoces, #firstblog

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)