In today’s article, we will learn to find subsets using bit masking. Bit masking is a very effective concept that can immensely help to optimize the code. We use bit masking to solve and optimize various problems like the N-Queens and today we’re here with another example making use of bitmasking. Without any further delay, let’s start learning.

## What Are Sub-sequences?

A subsequence is a combination that can be formed by using any number of elements from a given sequence. While forming a subsequence from a sequence, we have two options for every element. Either we select this element as part of the subsequence, or we don’t, there’s no way around it.

As for every element we have 2 fundamental choices, which explains that the total number of subsequences for any sequence is 2^{N}. Here N denotes the total number of elements in the subsequence.

One very basic difference between a substring and a subsequence is that substrings are continuous while subsequences are not.

## Concept of Subsets and Bitmasking

In this article, we will limit our code to string-based sequences. Though the approach for all types of sequences is similar, we will only be working with strings.

### Generating A Subsequence

For every character of the string, we have two options

- We select this element.
- Or we drop this element.

For the sake of understanding, let’s denote inclusion using 1 and exclusion using 0.

For example

```
Let's generate the subsets of "abc"
Total number of characters = 3
Hence, subsequences possible = 2^3 = 8
The 8 subsequences and their notations are:
" " = 000
"a" = 001
"b" = 010
"c" = 100
"ab" = 011
"ac" = 101
"bc" = 110
"abc" = 111
```

Our idea is to write a function *filter* that will take N and the string as the input, and generate all the possible subsequences. Then we will just iterate over the range *0 to (2 ^{N} – 1)*. Every iteration will produce one subsequence of the given string. We will write the code in the following steps

- Run a for loop from i = 0 to i = 2
^{N}– 1 - Each value of i for this loop will denote a numerical equivalent of the subsequence
- Now we will visualize this decimal number in binary form
- Initialize an integer j with value 0. This variable will denote the position of a character
- To do this, we will use a while loop
- while(n > 0)

- Inside this while loop we will extract each high bit of the variable i(numerical denoting a particular subsequence)
- To extract the set bits from i number, we will use the following logic
- while(i > 0)
- int set_bit = (i & 1)
- i == i >> 1

- while(i > 0)
- While doing this, for each iteration we will increment j. This while loop will run for log
_{2}i times. - And whenever we encounter a set bit we will print the element present at the position j.

```
filter(int N, char *s)
for i <-- 0 to i <-- (1 << n - 1)
j <-- 0
while(n >0)
last_bit <-- (n &1)
if(last_bit)
cout << s[j]
j <-- j + 1
n = n >> 1
cout << endl
return
```

## Find Subsets Of A String Using Bit Masking in C++

Let’s now implement bitmasking in C++ by following the steps that we’ve discussed above.

```
#include <iostream>
#include <cstring>
using namespace std;
void filter(string s)
{
for(int i = 0; i < 1 << s.length(); i++)
{
int j = 0;
int n = i;
cout << "[";
while(n > 0)
{
if(n & 1)
cout << s[j];
j++;
n = n >> 1;
}
cout << "]" << endl;
}
return;
}
int main()
{
cout << "Enter a string" << endl;
string s;
cin >> s;
filter(s);
return 0;
}
```

## Output

## Conclusion

In this article, we learned to find subsequence using bit masking. We use bit masking especially when we have a monotonous working region(states 0 to 2^{N} in this case). Because using bit masking we can easily represent these values. That’s it for now, thanks for reading.

## References

To learn more about recursion or bit masking, you can refer to the following websites.

https://www.journaldev.com/55710/tower-of-hanoi-in-c-solved

https://www.journaldev.com/57960/fast-exponentiation-using-bit-masking-using-c