# 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 )
( )
``````