Subsets

Introduction

This blog will discuss the “subset” problem in which we have to find the power set of the set of elements of a given array with unique elements. Before jumping into the problem and the approaches to solve it, let’s discuss “what is a set and a power set?”.

A set is a collection of unique elements. In our problem, an array of unique integers is given, so we can call it a set, and we have to find its power set.

A power set of a given set is the collection of all the subsets of that set. For understanding this definition of “power set,” let’s see what a subset is.

A subset of a set A is defined as a set B, whose each element is also an element of set A.

After all, this information, are we ready for the problem?

Let's move to the problem statement of this problem.

Problem Statement

Now, let’s understand the “subsets” problem. In this problem, we have to print all the subsets of the set formed by the elements of a given array with unique elements.

Now, let’s take an example to make it more clear. Let us assume the given array of unique elements is arr = [0, 1, 2]. 

We have to print a 2-dimensional array of all the subsets of the set formed by the elements of "arr".

All the subsets of the set {0, 1, 2} are - {}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1,2}, {0, 1, 2}

So, we have to print them.

Recommended: Before moving towards the approach, give it a try by yourself on Coding Ninjas Studio.

Solution Intuition and Approach

Let’s consider the same example as above.

arr = [0, 1, 2]

For each element of the array, we have two choices -

1. Taking it into the subset
2. Not taking it into the subset.
    

So, for generating the solution, we can consider each element one by one and process it. While processing each element, we will make two different subsets - one by taking it into the subset and another by not taking it into the subset. 

Similarly, we can extend this intuition to a general case of an array with “N” unique elements. For generating all the subsets, we have two choices for each element. So, the total number of subsets formed will be 2N. As in the previous example, N = 3, so the total subsets formed are ‘8’. 

Thus, the approach to the solution is to consider one by one each element of the array and generate two cases - one by taking it into the subset and one by not taking it. After considering all the array elements, add the subset formed into the array of subsets and finally print the 2-dimensional array containing all the subsets.                                              

Algorithm

Step 1. Create a recursive function ‘generateSubsets()’ that will accept the below parameters -

1. “arr’’: The given array of integers
2. “curr”: Index of the current element
3. “n”: Total number of elements in the given array
4. “subset”: Vector of integers passed to store the subset generated. Please note that this vector is passed by address.
    

Step 2. Then write the base case of the recursive function. If “curr == n”, i.e., after traversing and taking decisions on each element, print the subset generated and return. Write a helper function, “printSubset()”, which will take the input of a vector of integers and print it.

Step 3.  For each element, we have two choices - either take it into the subset or don’t take it. So first, call the “generateSubsets()” for the next element without taking the current element in the subset.

Step 4. Next, take the current element into the subset and then call the “generateSubsets()” function for the next element.

Step 5. Finally, in the backtracking step, remove the current element from the subset after generating all the subsets which include that element.

C++ Code

#include <bits/stdc++.h>
using namespace std;

// Function to print the subset
void printSubset(vector<int> subset)
  {
   for(int i = 0; i < subset.size(); i++)
     {
      cout<<subset[i]<<" ";
     }
   cout<<endl;
  }
 
void generateSubsets(int arr[], int curr, int n, vector<int>& subset)
  {
     
      // After traversing the whole array, print the generated subset
   if(curr == n)
   {
       printSubset(subset);
     return;
   }
       
       // Don’t take the current element in the subset and move to the next
   generateSubsets(arr, curr + 1, n, subset);

       // Take the current element in the subset and then move to the next
   subset.push_back(arr[curr]);
   generateSubsets(arr, curr + 1, n, subset);

       // Backtrack and pop the element before moving to the next
   subset.pop_back();
  }

int main()
  {
   int arr[3] = {0, 1, 2};
   vector<int> subset;
   cout<<"All the subsets of the set containing the elements of arr are :"<<endl;
   generateSubsets(arr, 0, 3, subset);
  }

You can also try this code with Online C++ Compiler

Run Code

Output:

All the subsets of the set containing the elements of arr are :

2 
1 
1 2 
0 
0 2 
0 1 
0 1 2 

You can also try this code with Online C++ Compiler

Run Code

Algorithm Complexity 

Time Complexity: O(N * (2 ^ N))

As we are making two recursive calls for every element of the array for the two available cases, i.e. either to add it into the subset or not, the time complexity will be O(2 ^ N), where ‘N’ is the number of elements in the array. If we consider the time taken by the “printSubset()” function, which is called to print each subset, then the overall time complexity will be O(N * (2 ^ N)).

Space Complexity: O(N) 

We have used a vector of integers subset to store the current subset. It can have maximum ‘N’ elements. So, space complexity is O(N), where ‘N’ is the total number of elements in the array.

Let's wrap up this blog and move toward the FAQs section.