How to Generate a Power Set in Python with Bitmasks

Generate the power set of a small list using a bitmask approach, producing all possible subsets.

Medium Python 3.9+ Aug 9, 2026 Algorithms & data structures 14 views 0 copies

bitmask power set subset generation algorithms

Python code

21 lines

Python 3.9+

def power_set(items):
    """Generate the power set of a list using bitmask approach."""
    n = len(items)
    result = []
    
    for mask in range(1 << n):
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(items[i])
        result.append(subset)
    
    return result


if __name__ == "__main__":
    items = ["a", "b", "c"]
    subsets = power_set(items)
    for subset in subsets:
        print(subset)
    print(f"Total subsets: {len(subsets)}")

Output

stdout

[]
['a']
['b']
['a', 'b']
['c']
['a', 'c']
['b', 'c']
['a', 'b', 'c']
Total subsets: 8

How it works

The bitmask technique treats each subset as a binary number where each bit indicates whether the corresponding element is included. The outer loop iterates through all masks from 0 to 2^n - 1, and for each mask we check each bit with the & operator to decide which items to append. This works for small lists because the number of subsets grows exponentially (2^n). The result is deterministic, producing subsets in lexicographic order of their bit patterns.

Common mistakes

Using a list of strings but forgetting that items are appended in order of index, not sorted; the order depends on the original list.
For large n (over ~20), the 2^n subsets consume too much memory; consider generators instead.
Assuming the empty set is included — it is, because mask=0 yields an empty subset.

Variations

Use `itertools.combinations` to generate subsets of each length, producing a different order.
Convert the loop to a generator with `yield` to avoid storing all subsets at once.

Real-world use cases

Enumerating feature combinations for A/B testing when the number of features is small.
Generating all subsets of a set of conditions in brute-force search problems.
Building a truth table for Boolean logic expressions with a small number of variables.

How to Generate a Power Set in Python with Bitmasks

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes