1.
Introduction
2.
Solution Intuition and Approach
3.
Algorithm
3.1.
C++ code
3.2.
Algorithm Complexity
4.
4.1.
4.2.
How BitMasking is used to solve this question?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Subsets (ii)

Riya
1 upvote

## Introduction

This blog will discuss the “subset (ii)” problem in which we have to find all the non-empty unique subsets of the set of elements of a given array that may contain duplicate elements. Before jumping into the problem and the approaches to solve it, let’s discuss “what is a set and a subset?”.

A set is a collection of unique elements.

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

Now, let’s understand the “subsets (ii)” problem. In this problem, we have to print all the non-empty unique subsets of the set formed by the elements of a given array of integers. The array may contain duplicate elements, but the repeated subset should be considered only once while printing the unique subsets.

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

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

All the subsets of {0, 1, 1} are { }, {0}, {1}, {1}, {0, 1}, {0, 1}, {1, 1}, {0, 1, 1}. But {1} and {0, 1} are repeated and {} is an empty subset.

So, all the required unique subsets of the set {0, 1, 1} are - {0}, {1}, {0, 1}, {1, 1}, {0, 1, 1}

and we have to print them.

Also see, Data Structures

Recommended: Try the Problem yourself before moving on to the Solution

## Solution Intuition and Approach

If an array contains “n” elements, then the total number of subsets will be “2 ^ n” as for each element of the array, we have two choices - either take it into the subset or not take it. But as we know in this question, the given array may contain duplicate elements, so some subsets will be repeated.

For finding all the subsets, we can generate binary number representations from 0 to (2 ^ n - 1) and create a subset corresponding to each number. If the ith bit of the binary number is set, then take the ith element in the subset, else not take it in the subset. We can understand this in a more precise way by taking an example.

Let’s consider the same example as above.

arr = [0, 1, 1]

It has 3 elements and so the total number of subsets will be ‘8’. But as the array is containing duplicate elements, there will be some repeated subset.

Here we can see that {1} and {0, 1} are repeating, but we have to print them only once. We can create an unordered set of strings to store the subsets by generating them in the form of strings. We can use a unique character to separate two elements of the subset in their corresponding string form. If we insert the same string multiple times, the unordered set will store it only once. In this way, we will get all the unique subsets. So, we will finally print all the unique subsets after recovering them from their string form.

Let’s demonstrate this idea on our example which we have taken-

So, let be the unordered set. It will be initially empty.

Thus, we can see that in this way, we have got the set containing all the unique subsets in their string form. So, now we can print them by recovering them.

## 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;
}
}
}``````

``````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)).

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 ith bit is set, we will include the ith 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.