Print all subsets of a given Set or Array

Spread the love

Input: N = 3, Arr = [1, 2, 3]
Output: {}
               {1}
               {1, 2}
               {1, 2, 3}
               {1, 3}
               {2}
               {2, 3}
               {3}
Explanation: These are all the subsets that can be formed from the given array, it can be proven that no other subset exists other than the given output.


Input: N = 2, Arr = [2, 4]
Output: {}
               {2}
               {2, 4}
               {4}
Explanation: These are all the subsets that can be formed from the given array, it can be proven that no other subset exists other than the given output.

Table of Contents

How many Subsets are possible for an Array of size ‘N’ ?

Can we see a relationship of any sort between array N’s size and the number of subgroups it forms before diving into the solution? Yes, there is a relationship, as indicated by the following formula:

An array of size N = 2^N has how many subsets?

Proof: We have two options for each array element:

Option 1: Add it to the subset.
Option 2: Take it out of the subset.
Total subsets = 2^N since each element has two options for contributing to the subset and there are N elements in total.

Let’s examine how this observation can be used to build our solution.

Printing all subsets using Backtracking

To put the above concept into practice, take the actions listed below:

It adds an empty subset to the result list at the beginning.
The input vector’s elements are iterated through:
contains the element that is currently in the subset.
It calls itself recursively using the next index and the modified subset.
backtracks, removing the current member from the subset.

C++

#include <iostream>
#include <vector>
using namespace std;

void calcSubset(vector<int>& A, vector<vector<int> >& res,
                vector<int>& subset, int index)
{
    // Add the current subset to the result list
    res.push_back(subset);

    // Generate subsets by recursively including and
    // excluding elements
    for (int i = index; i < A.size(); i++) {
        // Include the current element in the subset
        subset.push_back(A[i]);

        // Recursively generate subsets with the current
        // element included
        calcSubset(A, res, subset, i + 1);

        // Exclude the current element from the subset
        // (backtracking)
        subset.pop_back();
    }
}

vector<vector<int> > subsets(vector<int>& A)
{
    vector<int> subset;
    vector<vector<int> > res;
    int index = 0;
    calcSubset(A, res, subset, index);
    return res;
}

// Driver code
int main()
{
    vector<int> array = { 1, 2, 3 };
    vector<vector<int> > res = subsets(array);

    // Print the generated subsets
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++)
            cout << res[i][j] << " ";
        cout << endl;
    }

    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;

public class Subsets {
    public static void calcSubset(List<Integer> A,
                                  List<List<Integer> > res,
                                  List<Integer> subset,
                                  int index)
    {
        // Add the current subset to the result list
        res.add(new ArrayList<>(subset));

        // Generate subsets by recursively including and
        // excluding elements
        for (int i = index; i < A.size(); i++) {
            // Include the current element in the subset
            subset.add(A.get(i));

            // Recursively generate subsets with the current
            // element included
            calcSubset(A, res, subset, i + 1);

            // Exclude the current element from the subset
            // (backtracking)
            subset.remove(subset.size() - 1);
        }
    }

    public static List<List<Integer> >
    subsets(List<Integer> A)
    {
        List<Integer> subset = new ArrayList<>();
        List<List<Integer> > res = new ArrayList<>();

        int index = 0;
        calcSubset(A, res, subset, index);

        return res;
    }

    // Driver code

    public static void main(String[] args)
    {
        List<Integer> array = List.of(1, 2, 3);
        List<List<Integer> > res = subsets(array);

        // Print the generated subsets
        for (List<Integer> subset : res) {
            for (Integer num : subset) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}

Python

def calcSubset(A, res, subset, index):
    # Add the current subset to the result list
    res.append(subset[:])

    # Generate subsets by recursively including and excluding elements
    for i in range(index, len(A)):
        # Include the current element in the subset
        subset.append(A[i])

        # Recursively generate subsets with the current element included
        calcSubset(A, res, subset, i + 1)

        # Exclude the current element from the subset (backtracking)
        subset.pop()


def subsets(A):
    subset = []
    res = []
    index = 0
    calcSubset(A, res, subset, index)
    return res


# Driver code
if __name__ == "__main__":
    array = [1, 2, 3]
    res = subsets(array)

    # Print the generated subsets
    for subset in res:
        print(*subset)

JavaScript

function calcSubset(A, res, subset, index) {
    // Add the current subset to the result list
    res.push([...subset]);

    // Generate subsets by recursively including and excluding elements
    for (let i = index; i < A.length; i++) {
        // Include the current element in the subset
        subset.push(A[i]);

        // Recursively generate subsets with the current element included
        calcSubset(A, res, subset, i + 1);

        // Exclude the current element from the subset (backtracking)
        subset.pop();
    }
}

function subsets(A) {
    const subset = [];
    const res = [];
    let index = 0;
    calcSubset(A, res, subset, index);
    return res;
}

// Driver code
function main() {
    const array = [1, 2, 3];
    const res = subsets(array);

    // Print the generated subsets
    for (let i = 0; i < res.length; i++) {
        console.log(res[i].join(' '));
    }
}

// Call the main function
main();

Output

Complexity Analysis:

Time Complexity: O(N*2^N), where n is the size of given array.
Auxiliary Space: O(N * 2^N)
- O(N) : if we only print our subsets, there will at max N recursion stack
- O(2^N) : if we would store all the subsets we will need 2^N memory blocks to store each subset