# Bitmasking: Generating Subsets Iteratively

The typical method of generating all subsets of a set is recursion/backtracking. However, just as easily (if not easier), we can do this with another method: bitmask. 

The premise is that every number has a unique binary representation. If we look at generating all subsets of a set constructively, each element will either appear or not appear in the set. If we let "appear" be the bit 1 and "not appear" be the bit 0, we can create the following bijection: 

For any set `S`, let `|S|` denote its size. Every subset of `S` (including the empty set) can be viewed constructively as a string of bits (1 for "appear" and 0 for "not appear"), where the bit in the `k`th position corresponds to whether or not the `k`th element of `S` appears in a constructed subset. 

But a greater revelation follows: if we iterate through all binary numbers `000...0` to `111...1` (where `|S|` bits are explicitly enumerated), we essentially iterate over all possible subset constructions. Then, if we further want to explicitly generate each subset (to get what is called the power set of `S`), we can simply emplace the elements to a vector and clear it as we go. Each of these binary numbers corresponds to (or "bitmasks") a construction.

As an implementation detail, since we write binary numbers in their decimal form, we are actually iterating from the decimal number `0` to the decimal number `2^|S| - 1`. We can check to see when bits are 1 through the right shift operator and \&ing the result with 1. 

Below is a sample implementation for all non-empty subsets of `{1,2,3,4,5}`. Note that we only print non-empty subsets since the empty set would not display (and is trivial).

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

template<class T> void out(T a, T b) { 
    assert(a != b); 
    while(b - a - 1) cout << *a << " ", ++a; 
    cout << *--b << "\n";
} 
// function to easily output the result

vector<int> S = {1, 2, 3, 4, 5}; // original set
int sz = S.size(); // |S|

vector<int> s; // we will use this to store generated subsets
int ctr; // we can also count the total number of subsets

int main() {
    for(int i = 0; i < (1 << sz); ++i) { // iterate over "bitmasks"
        for(int j = 0; j < sz; ++j) // iterate over amount to right shift
            if((i >> j) & 1) s.emplace_back(S[j]); // generate s constructively
        if(s.size()) out(begin(s),end(s)); // print non-empty subsets
        ++ctr; // count each subset (including the empty set)
        s.clear(); // clear s to make way for a new subset
    }
    cout << "Overall, there are " << ctr << " subsets,";
    cout << " including the empty set.\n";
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aryansh.gitbook.io/informatics-notes/misc-tricks/bitmask-subsets.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.