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

This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org

"The most disastrous thing that you can ever learn is your first programming language. - Alan Kay"