Generating Subsets Using Bitmasks

A subset of an sequence is a set constructed from some elements of the sequence (maybe none). for an sequence {1, 3, 5, 6, 7} sets like {1, 3}, {3, 5, 7}, and {1, 3, 5, 6, 7} are subsets of the sequence, while sets like {1, 4}, {2, 7} are not subsets of the sequence

Encoding Subsets as Binary Numbers

For a sequence of length \(n\), we can represent each of its subsets using an \(n\)-bit binary number. In this representation, a bit is set to \(1\) if the corresponding element is included in the subset, and \(0\) if it is not.

For example, consider the sequence {5, 3, 1}. The binary encodings of its subsets are:

Subset of {5, 3, 1}	Encoding (Binary)	Encoding (Decimal)
{}	000	0
{5}	001	1
{3}	010	2
{5, 3}	011	3
{1}	100	4
{5, 1}	101	5
{3, 1}	110	6
{5, 3, 1}	111	7

Note

For an sequence of length \(n\) the number of different subsets is \(2^n\).

Generating Subsets

We can observe that for a sequence of length \(n\), all subsets can be numbered from \(0\) to \(2^n - 1\). Using this numbering, we can loop over all integers from \(0\) to \(2^n - 1\) and generate each subset by checking which bits are set.

For example, suppose we want to write code that prints all subsets of a sequence a, each on a separate line.

#include <iostream>
using namespace std;

int main() {
  int n = 3;
  int a[3] = {5, 3, 1};

  for(int i = 0; i < (1 << n); i++) {   // loops over all subsets from 0 to 2^n - 1.
    cout << i << ": ";

    for(int j = 0; j < n; j++) {        // loops over all bits
      bool set = (i & (1 << j)) != 0;   // checks if the j-th bit is set in i. 
      if(set) {
        cout << a[j] << ' ';
      }
    }

    cout << endl;
  }
}

The output will be:

0: 
1: 5 
2: 3 
3: 5 3 
4: 1 
5: 5 1 
6: 3 1 
7: 5 3 1