Generating subsets or combinations using recursion

Generating subsets or combinations using recursion

This approach for generating subsets uses recursion and generates all the subsets of a superset [ 1, 2, 3, …, N ].
The function Generate_Subsets maintains a list / vector to store the elements of each subset. During the function’s execution, it evaluates two cases
1. Element ‘R’ is included in the subset and a next subset is generated.
2. Element ‘R’ is not included in the subset and a next subset is generated.

The calls begins with Generate_Subsets ( 1 ), i.e with R = 1 being the first element to be included in the subset.


Algorithm : Generate subsets using recursion
Superset of size N.
1.   Generate_Subsets ( int R )
2.       If ( R == N+1 )
3.          Process the subset V.
4.       Else
5.           Include R in the subset and generate next subset
              V . push_back ( R );
              Generate_Subsets ( R + 1 );
6.           Do not include R in the subset and generate next subset
              V . pop_back ( );
              Generate_Subsets ( R + 1 );


The idea behind generating subsets using recursion is explained using the below recursion stack.
Example : Consider a super-set containing elements [ 1, 2 ].
Subset 1 : [ 1, 2 ]
Subset 2 : [ 1 ]
Subset 3 : [ 2 ]
Subset 4 : [ ]

Below recursion stack explains how the algorithm for generating subsets using recursion works

Steps Call stack Element R in function call Operations Subset
1 Function call 1 1 Push 1 into the subset.
Make function call 2, with R = 2
[ 1 ]
2 Function call 2 2 Push 2 into the subset.
Make function call 3, with R = 3
[ 1, 2 ]
3 Function call 3 3 R = 3 is greater than the size ( 2 ) of super set.
Print the subset [ 1, 2 ]
Return
[ 1, 2 ]
4 Function call 2 2 Pop 2 from the subset. Make function call 4, with R = 3 [ 1 ]
5 Function call 4 3 R = 3 is greater than the size ( 2 ) of super set.
Print the subset [ 1 ]
Return
[ 1 ]
6 Function call 2 2 Return. [ 1 ]
7 Function call 1 1 Pop 1 from the subset. Make function call 5, with R = 2 [ ]
8 Function call 5 2 Push 2 into the subset. Make function call 6, with R = 3 [ 2 ]
9 Function call 6 3 R = 3 is greater than the size ( 2 ) of super set.
Print the subset [ 2 ]
Return
[ 2 ]
10 Function call 5 2 Pop 2 from the subset. Make function call 7, with R = 3 [ ]
11 Function call 7 3 Element count ( 3 ) is greater than the size ( 2 ) of super set.
Print the subset [ ]
Return
[ ]

Python3 : Generating subsets or combinations using recursion

C++14 : Generating subsets or combinations using recursion

#include<iostream>
#include<vector>

using namespace std;

class Superset {

    private:
    int size; // Size of superset.
    vector<int> subset;

    public:
    Superset (int arg_size) : size(arg_size) {}

    // Generating subsets / combinations using recursion.
    void GenerateSubset (int num) {

       if ( num > size ) {
           cout << "( ";
           for (const auto& item : subset) {
               cout << item << " ";
           } cout << ")" << endl;
       } else {

           subset.push_back(num);
           GenerateSubset(num+1);

           subset.pop_back();
           GenerateSubset(num+1);
       }
    }

    int GetSize() {
        return size;
    }
};

int main() {

    Superset S1(4);
    cout << "All subsets within superset of size : " << S1.GetSize() << endl;
    S1.GenerateSubset(1);

    Superset S2(2);
    cout << "All subsets within superset of size : " << S2.GetSize() << endl;
    S2.GenerateSubset(1);

    return 0;
}

Output

All subsets within superset of size : 4
( 1 2 3 4 )
( 1 2 3 )
( 1 2 4 )
( 1 2 )
( 1 3 4 )
( 1 3 )
( 1 4 )
( 1 )
( 2 3 4 )
( 2 3 )
( 2 4 )
( 2 )
( 3 4 )
( 3 )
( 4 )
( )
All subsets within superset of size : 2
( 1 2 )
( 1 )
( 2 )
( )

Copyright © 2019-2020, Algotree.org.
All rights reserved.