Introduction

The power set of a list is the set of all possible subsets of its elements, including the empty subset and the full list itself. If the list has n elements, the power set has 2^n subsets. That exponential growth is the most important fact about this problem, because it means even a perfect algorithm becomes expensive quickly as n grows.

A Bitmask Approach

A common way to generate the power set is to treat each subset as a bitmask. Each bit says whether the corresponding element is included.

1def power_set(items):
2    result = []
3    n = len(items)
4    for mask in range(1 << n):
5        subset = [items[i] for i in range(n) if mask & (1 << i)]
6        result.append(subset)
7    return result
8
9print(power_set(["a", "b", "c"]))

This is a clean iterative solution because the binary numbers from 0 to 2^n - 1 already encode every possible inclusion pattern.

A Recursive Approach

Another classic approach is recursion: for each element, either include it or exclude it.

1def power_set_recursive(items):
2    if not items:
3        return [[]]
4
5    first = items[0]
6    rest_power = power_set_recursive(items[1:])
7    with_first = [[first] + subset for subset in rest_power]
8    return rest_power + with_first
9
10print(power_set_recursive([1, 2, 3]))

This mirrors the mathematical definition nicely and is often easier to explain in interviews or teaching contexts.

Use itertools When You Want Combinations by Size

In Python, itertools.combinations makes it easy to generate subsets grouped by size.

1from itertools import combinations
2
3
4def power_set_itertools(items):
5    result = []
6    for r in range(len(items) + 1):
7        result.extend(combinations(items, r))
8    return result
9
10print(power_set_itertools(["x", "y", "z"]))

This returns tuples rather than lists, but it is concise and expressive.

It is especially useful when you care about subset sizes or want to iterate lazily rather than materializing everything immediately.

Complexity Matters More Than the Loop Style

No matter which approach you choose, generating the full power set has exponential output size.

If the input has:

• 3 elements, there are 8 subsets
• 10 elements, there are 1024 subsets
• 20 elements, there are over 1 million subsets

That means the real performance question is usually not "bitmask or recursion" but "do I really need the full power set."

If you only need subsets up to a certain size, generate only those combinations instead of the entire power set.

Ordering and Duplicates

The power set is usually defined for a set, but code often receives a list. If the input list contains duplicates, the generated subsets may also contain duplicates in positional form.

print(power_set(["a", "a"]))

If uniqueness matters mathematically, deduplicate the input first or normalize the output representation.

That is not an implementation bug. It is a difference between list semantics and set semantics.

Common Pitfalls

The most common mistake is forgetting the exponential growth and then trying to generate the full power set for a large input.

Another issue is assuming the input behaves like a mathematical set even when it is really a list with duplicates.

Developers also sometimes choose a recursive approach without considering recursion depth or readability tradeoffs for larger inputs.

Finally, if you only need subsets of a particular size, do not generate the entire power set and then throw most of it away.

Summary

• The power set contains all subsets, so a list of n elements produces 2^n subsets.
• Bitmasking is a clean iterative implementation.
• Recursion matches the mathematical definition nicely.
• 'itertools.combinations is ideal when you want subsets by size.'
• Always think about exponential growth before generating the full result.