Introduction

Generating every subset of a set, also called the power set, is a common building block in combinatorics, brute-force search, and feature selection. The core algorithms are straightforward, but the real constraint is exponential growth: a set with n elements has 2^n subsets, so the output size dominates everything else.

Understand the Size Before Choosing an Algorithm

For small inputs, almost any correct method is fine. For larger inputs, the number of subsets explodes quickly:

1. n = 10 produces 1024 subsets
2. n = 20 produces 1,048,576 subsets

That means no implementation can be “fast” in the usual sense once the input grows. The best you can do is choose a clear method, avoid unnecessary overhead, and generate lazily when possible.

Iterative Doubling Is Simple and Readable

A clean iterative method starts with the empty subset and, for each item, adds a copy of every existing subset with that item included.

1def power_set_iter(items):
2    subsets = [[]]
3
4    for item in items:
5        subsets += [subset + [item] for subset in subsets]
6
7    return subsets
8
9
10print(power_set_iter([1, 2, 3]))

This version is excellent for teaching and for small-to-medium inputs where clarity matters most.

Bitmask Generation Is Compact and Deterministic

Each subset can be represented by a bitmask where each bit says whether the corresponding item is present.

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

Bitmasks are convenient when you also need numeric representations for search or caching. They also guarantee a stable ordering based on mask order.

Recursive Backtracking Is Easy To Extend

Backtracking is another common solution. At each position, decide whether to include the current element, then recurse to the next position.

1def power_set_dfs(items):
2    result = []
3
4    def dfs(i, current):
5        if i == len(items):
6            result.append(current.copy())
7            return
8
9        dfs(i + 1, current)
10        current.append(items[i])
11        dfs(i + 1, current)
12        current.pop()
13
14    dfs(0, [])
15    return result
16
17
18print(power_set_dfs([1, 2, 3]))

This style is especially useful when you later want to add pruning rules, subset-size limits, or constraints on valid combinations.

Generate Lazily When You Do Not Need Everything at Once

If the consumer can process subsets one by one, a generator reduces peak memory use dramatically.

1def power_set_lazy(items):
2    n = len(items)
3
4    for mask in range(1 << n):
5        yield [items[i] for i in range(n) if mask & (1 << i)]
6
7
8for subset in power_set_lazy([1, 2, 3]):
9    print(subset)

This does not change the total amount of work, but it keeps you from storing the whole power set in memory at the same time.

Generate Only the Subsets You Actually Need

Many real tasks do not need every subset. If you only need subsets of size k, use a constrained generator such as itertools.combinations.

1from itertools import combinations
2
3def subsets_of_size(items, k):
4    return [list(group) for group in combinations(items, k)]
5
6
7print(subsets_of_size([1, 2, 3, 4], 2))

This is often the difference between a practical solution and an accidental exponential blow-up.

Validate Count and Ordering Assumptions

Different algorithms produce subsets in different orders. If another part of the program depends on output order, define that contract explicitly and test it. At a minimum, verify the count and a few key members.

1items = [1, 2, 3]
2subsets = power_set_iter(items)
3
4assert len(subsets) == 2 ** len(items)
5assert [] in subsets
6assert items in subsets

These checks are simple but catch many refactoring mistakes.

Common Pitfalls

The biggest mistake is ignoring exponential growth and exposing subset generation without input limits. Another is assuming all algorithms produce subsets in the same order. Developers also generate a full power set when they only need fixed-size combinations, which wastes both time and memory.

Summary

• Power-set generation is inherently exponential because the output size is 2^n.
• Iterative doubling, bitmasks, and backtracking are all valid core techniques.
• Use lazy generation when the consumer does not need all subsets at once.
• Prefer constrained methods such as combinations when only fixed-size subsets are required.
• Define output-order expectations and add input-size limits for production use.