Subsets (ii)

Algorithm 

Step 1. Create a function “generateUniqueSubsets()” that will accept the below parameters -

1. “arr’’: The given array of integers
2. “n”: Total number of elements in the given array
3. “subsets”: An unordered set of strings to store the generated subsets in their string form. Note that it is passed by address so that we can insert strings in it inside this function. 

Step 2. Create a “for loop” to run from 0 to (2 ^ n - 1) to generate a subset corresponding to each number.

Step 3.  Inside the previous “for loop”, create another “for loop” to run from 0 to n to check each bit of the number. If the jth bit is set, then add the jth element into the subset. After generating each subset, insert it into the set of subsets passed as a parameter in the function.

Step 4.  Now recover each subset from their string form and print it. Create a function “split,” which will take input the generated string and delimiter used and split the string into elements of the subset. So, finally, print the subset.

C++ code

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

vector<string> split(const string &s, char delimiter)
{
    vector<string> uniqueSubset;
    stringstream ss(s);
    string element;
    while (getline(ss, element, delimiter))
        uniqueSubset.push_back(element);
 
    return uniqueSubset;
}

void generateUniqueSubsets(int arr[], int n, unordered_set<string>& subsets)
  {

       // For loop to consider one by one each number from 0 to (2 ^ n - 1)
   for(int i = 0; i < int(pow(2, n)); i++)
     {
      string subset="";

             // For loop to one by one check each bit of the number
      for(int j = 0; j < n; j++)
        {
                     
                    // If the jth bit is set, add the jth element in the subset
         if((i & (1 << j)) != 0) {
           subset += to_string(arr[j]) + '@';
         }
        }
             
             // Insert the subset generated into the set of subsets
      subsets.insert(subset);
     }
  }

int main()
  {
   int arr[3] = {0, 1, 1};

       // Unordered set to store all unique subsets in their string form
   unordered_set<string> subsets;
       
       // Calling the function to generate all the unique subsets
   generateUniqueSubsets(arr, 3, subsets);

   cout<<"All the subsets of the set containing the elements of arr are :"<<endl;

       // Recovering each subset from their string form
   for (string subset : subsets)
         {

             /*
                 Calling the split function to recover the subset by removing
                 The delimiter and getting all the elements of the subset
             */
             vector<string> uniqueSubset = split(subset, '@');

             // Checking that the subset should be non-empty
             if(uniqueSubset.size()>0) {
                for (string str: uniqueSubset)
                cout << str << " ";
                cout << endl;
             }
         }
  }

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 :
0 1 1 
1 
0 1 
1 1 
0 

Algorithm Complexity

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

In the function “generateUniqueSubsets()”, a for loop is created to run from 0 to 2 ^ n, and inside it, another for loop of 0 to n is created for checking each bit. So, the overall time complexity is O(N * (2 ^ N)), where ‘N’ is the number of elements in the given array. 

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

We have used a set of strings to store string representations of all the subsets. For an array of ‘N’ elements, the maximum number of subsets that can be generated are (2 ^ N) and the maximum length of a string form of a subset can be N. So,  the space complexity is O(N * (2 ^ N)).

Frequently Asked Questions

What is BitMasking?

Bitmasking is a technique used in programming. In it we use binary representation of a number, its bytes information whether it is set or not, and use some bitwise operators for getting our required solution.

How BitMasking is used to solve this question?

In this question, we have to generate all unique subsets. We can see here that for generating a subset with ‘n’ number of elements, we have two choices for each element - either include it in the subset or not. If we will consider all the n-bit binary numbers, for each bit, we also have two choices - either it is set or not. So, we can use this for generating all the subsets. We will consider one by one each n-bit binary number and if the i^th bit is set, we will include the i^th bit element in the subset and vice versa. And finally, we have used a set of strings and stored the string form of each subset in it to get all the unique subsets.

Conclusion

In this article, we discussed what the “subset (ii)” problem is, discussed the BitMasking approach to solve this problem programmatically, and discussed the time and space complexities. If you want to practice this problem, then you can visit Coding Ninjas Studio.

Recommended Readings:

• Additive Numbers
• Print All Permutations of A String
• Backtracking and Recursion
• Minimum Subset Sum Difference
• Bit Manipulation
• Permutation of string

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!