Enumerating All Subsets

A subset of $n$ elements can be represented as an $n$-bit integer. Bit $i$ is $1$ if element $i$ is included.

for mask from 0 to 2^n - 1:
    subset = []
    for i from 0 to n-1:
        if mask & (1 << i):
            subset.add(elements[i])
    // process subset

Example: $n = 3$, elements $[a, b, c]$.

• mask $= 0$ (binary $000$): $[]$
• mask $= 1$ (binary $001$): $[a]$
• mask $= 5$ (binary $101$): $[a, c]$
• mask $= 7$ (binary $111$): $[a, b, c]$

Time: $O(n \cdot 2^n)$. Generate all $2^n$ subsets, each takes $O(n)$ to process.