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 kth position corresponds to whether or not the kth 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).

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