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

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



Copyright (c) 2019-2021, Algotree.org.
All rights reserved.