# 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
[ ]

Program for recursively generating subsets or combinations

``````#!/usr/bin/python3

def GenerateSubset (R) :
if (R > N) :
# Process the subset
print("[ "+' '.join ( map (str,subset) ) + " ]")
else :
# Generate subset with R
subset.append(R)
GenerateSubset (R + 1)

# Generate subset without R
subset.pop()
GenerateSubset (R + 1)

# Generating subsets / combinations using recursion.
R = 1
subset = []

N = 4
print("Subsets for set 1: ")
GenerateSubset (R)

N = 2
print("Subsets for set 2: ")
GenerateSubset (R)
``````

Output

``````Subsets for set 1:
[ 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 ]
[  ]
Subsets for set 2:
[ 1 2 ]
[ 1 ]
[ 2 ]
[  ]
``````
``````#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 )
( )
``````
``````import java.util.*;

class Superset {

private int size; // Size of superset.
private ArrayList<Integer> subset = new ArrayList<Integer> ();

Superset ( int s ) {
size = s;
}

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

if ( num > size ) {

System.out.print ( "( " );

for ( int i = 0; i < subset.size(); i++ ) {
System.out.print ( subset.get(i) + " " );
}

System.out.println (")");

} else {

GenerateSubset ( num + 1 );

subset.remove ( subset.size() - 1 );
GenerateSubset ( num + 1 );
}
}

public int GetSize() {
return size;
}

public static void main(String[] args) {

Superset S1 = new Superset(4);
System.out.println( "All subsets within superset of size : " + S1.GetSize() );
S1.GenerateSubset(1);

Superset S2 = new Superset(2);
System.out.println( "All subsets within superset of size : " + S2.GetSize() );
S2.GenerateSubset(1);
}
}
``````

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