Introduction

Generating all subsets of a collection is the classic powerset problem. It shows up in brute-force search, combinatorics, feature selection, and test generation, and the implementation changes slightly when the input can contain duplicate values.

Know the Size Before You Start

If the input has n distinct elements, the powerset contains 2 ** n subsets. That exponential growth is unavoidable because the output itself is that large.

For a three-item input, you get:

• one empty subset
• three one-item subsets
• three two-item subsets
• one full subset

That is why powerset code feels simple for small inputs but becomes expensive quickly as n grows.

Build the Powerset Iteratively

The clearest solution starts with the empty subset and then duplicates the current list of subsets for each new value, once without the value and once with it.

1def powerset(values):
2    subsets = [[]]
3
4    for value in values:
5        new_subsets = [subset + [value] for subset in subsets]
6        subsets.extend(new_subsets)
7
8    return subsets
9
10
11items = ["a", "b", "c"]
12for subset in powerset(items):
13    print(subset)

This version is easy to read because it directly models the include-or-skip choice for each element.

Use Recursion When You Want a Mathematical Form

Recursion expresses the same idea more explicitly: compute the powerset of the remaining values, then prepend the first value to each of those subsets.

1def recursive_powerset(values):
2    if not values:
3        return [[]]
4
5    first = values[0]
6    rest = recursive_powerset(values[1:])
7    with_first = [[first] + subset for subset in rest]
8
9    return rest + with_first
10
11
12print(recursive_powerset([1, 2, 3]))

The recursive form is elegant, but the iterative version is usually easier to debug and avoids recursion depth concerns for larger inputs.

Handle Duplicate Input Values

The word "set" suggests unique elements, but many real inputs are lists like [1, 2, 2]. A naive powerset algorithm will generate duplicate subsets for that input because the two copies of 2 are treated as separate positions.

If you want unique subsets, sort the input and skip repeated values at the same search depth.

1def unique_subsets(values):
2    values = sorted(values)
3    result = []
4
5    def backtrack(start, current):
6        result.append(current[:])
7
8        for i in range(start, len(values)):
9            if i > start and values[i] == values[i - 1]:
10                continue
11
12            current.append(values[i])
13            backtrack(i + 1, current)
14            current.pop()
15
16    backtrack(0, [])
17    return result
18
19
20print(unique_subsets([1, 2, 2]))

That duplicate check is the important part. It prevents repeated branches without removing valid subsets that happen to contain the repeated value.

Use Bitmasks for Index-Based Problems

Another common approach is to use a binary mask. Every number from 0 to 2 ** n - 1 represents one subset, and each bit says whether the corresponding element is included.

1def bitmask_powerset(values):
2    result = []
3    n = len(values)
4
5    for mask in range(1 << n):
6        subset = [values[i] for i in range(n) if mask & (1 << i)]
7        result.append(subset)
8
9    return result
10
11
12print(bitmask_powerset(["x", "y", "z"]))

This method is especially useful in optimization code where subsets are naturally represented as compact integer states.

Common Pitfalls

The first mistake is underestimating output size. Once the input reaches 20 distinct items, you already have more than one million subsets, which can overwhelm memory or runtime.

Another common bug appears in backtracking solutions that append the same mutable list object repeatedly. Always store a copy such as current[:], or later changes will corrupt earlier results.

Duplicate handling is another source of confusion. If the input is conceptually a set, normalize it first. If duplicates are meaningful, decide whether repeated subsets are acceptable or whether you need the deduplicated backtracking approach.

Finally, do not depend on subset order unless your algorithm truly requires it. Iterative, recursive, and bitmask solutions all produce correct subsets, but not necessarily in the same sequence.

Summary

• A powerset has 2 ** n subsets for n distinct elements.
• Iterative, recursive, and bitmask methods all solve the same core problem.
• Duplicate values need extra handling if you want unique subsets.
• Backtracking code should save copies of partial subsets, not shared references.
• The main limit is the size of the output, not the elegance of the implementation.