Subsets via bitmask

Generate every subset of a small array by reading each number from 0 to 2^n - 1 as a bitmask of inclusions.

Time O(n * 2^n)Space O(1) extraCode C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Each of the n elements is either in a subset or not, which is exactly one bit of information, so every subset corresponds to a unique n-bit number. Counting mask from 0 to 2^n - 1 visits every combination of bits exactly once, and bit i of mask says whether a[i] belongs to that subset.

Code

public static List<List<int>> SubsetsByBitmask(int[] a) {
    var result = new List<List<int>>();
    int n = a.Length;
    for (int mask = 0; mask < (1 << n); mask++) {
        var subset = new List<int>();
        for (int i = 0; i < n; i++)
            if ((mask & (1 << i)) != 0)
                subset.Add(a[i]);
        result.Add(subset);
    }
    return result;
}

Tips

mask & (1 << i) tests bit i without disturbing the other bits.
mask = 0 always gives the empty subset and mask = 2^n - 1 always gives the full set.

In the .NET library

This is the same search space as the recursive Subsets lesson in Backtracking; the bitmask version just enumerates it iteratively instead of with recursive choices.