CODEWITHSUNDEEP
c++recursion
Vishal Arya
Vishal Arya

Reputation: 11

What are the steps involved in the execution of the program which generates the subset of a given set (using recursion)?

Program for subsets of a set

#include <bits/stdc++.h>
using namespace std;

vector<int> subset;
int n = 3;
void search(int k) {
    if (k == n) {
        cout << "{ ";
        for (auto x : subset) {
            cout << x;
            if ( x != subset.back() )
                cout << ", ";
        }
        cout << " } ";
    }
    else {
        search(k+1);           //**Explanation**
        subset.push_back(k);   // **for** 
        search(k+1);           //**these** 
        subset.pop_back();     //**statements**
    }
}

int main() {
    int k = 0;
    search(k);
}

I can't understand the code given in the else section.

o/p:-

 {  } { 2 } { 1 } { 1, 2 } { 0 } { 0, 2 } { 0, 1 } { 0, 1, 2 }

Upvotes: 0

Views: 67

Answers (1)

Garf365
Garf365

Reputation: 3707

With this kind of issue, sometime, better way is to take a pen and a sheet and to "execute" software by hand:

  • call search(0) (subset = { })
    • call search(1) (subset = { })
      • call search(2) (subset = { })
        • call search(3) (subset = { })
          • print subset (subset = { })
        • push back 2 in subset (subset = { 2 })
        • call search(3) (subset = { 2 })
          • print subset (subset = { 2 })
        • remove last element (subset = { })

          When you come back to search(1), subset still in same state as before call of search(2)

      • push back 1 in subset (subset = { 1 })
      • call search(2) (subset = { 1 })
        • call search(3) (subset = { 1 })
          • print subset (subset = { 1 })
        • push back 2 in subset (subset = { 1, 2 })
        • call search(3) (subset = { 1, 2 })
          • print subset (subset = { 1, 2 })
        • remove last element (subset = { 1 })

          When you come back to search(1), subset still in same state as before call of search(2)

      • remove last element (subset = { })

        When you come back to search(0), subset still in same state as before call of search(1)

    • push back 0 in subset (subset = { 0 })
    • call search(1) (subset = { 0 })
      • call search(2) (subset = { 0 })
        • call search(3) (subset = { 0 })
          • print subset (subset = { 0 })
        • push back 2 in subset (subset = { 0, 2 })
        • call search(3) (subset = { 0, 2 })
          • print subset (subset = { 0, 2 })
        • remove last element (subset = { 0 })

          When you come back to search(1), subset still in same state as before call of search(2)

      • push back 1 in subset (subset = { 0, 1 })
      • call search(2)(subset = { 0, 1 })
        • call search(3)(subset = { 0, 1 })
          • print subset (subset = { 0, 1 })
        • push back 2 in subset (subset = { 0, 1, 2 })
        • call search(3) (subset = { 0, 1, 2 })
          • print subset (subset = { 0, 1, 2 })
        • remove last element (subset = { 0, 1 })

          When you come back to search(1), subset still in same state as before call of search(2)

      • remove last element (subset = { 0 })

        When you come back to search(0), subset still in same state as before call of search(1)

    • remove last element (subset = { })

      When you come back to main, subset still in same state as before call of search(0)

With that, we can see that push_back is for populate subset and pop_back is for cleaning/undoing action maid by this step. Indeed, you use a global variable, used also by previous call of this function. In this algorithm, you have to clean it to restore state of this variable for caller. It would be different if you pass subset by value.

Upvotes: 1

Related Questions