Algotree > Algorithms > Recursive Algorithms 🌀 🌀 🌀 > Generating subsets or combinations using recursion

Generating subsets or combinations using recursion

The approach for generating all subsets a superset [ 1, 2, 3, …, N ] is as follows.

The recursive function Generate_Subsets keeps a list to store the elements in a subset. The function gets called seperately for the below two cases
1. An element R is included in the subset and a next subset is generated.
2. An 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.          The last element has been included in the subset. Now print the subset V.
4.       Else
5.           Include R in the subset and generate next subset
              Add R to the subset. i.e V . push_back ( R )
              Generate_Subsets ( R + 1 )
6.           Do not include R in the subset and generate next subset
              Remove R that was added earlier. i.e 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 {

            subset.add (num);
            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 )
( )